Qədim sülalələr
Tatar-monqol xanlığının zəngin hökmdarları haqqında maraqlı bir tarix var. Bu hökmdarlar iki sülalədən birinə mənsub idi və hakimiyyət tez-tez bir sülalədən digərinə keçirdi. Hər bir hökmdarın taxta çıxması 26 mart tarixində keçirilən bayramla qeyd olunurdu. Salnamələrdə bu bayramların keçirildiyi illər qeyd olunmuşdur və məlumdur ki, birinci sülalənin hökmdarları xalq üçün qımız bayramı, ikinci sülalənin hökmdarları isə bal bayramı təşkil edirdilər.
Tatar-monqol xanlığının tarixi üzrə konfransda hər bir s alim salnamənin öz versiyasını təklif etdi. Yəni, i-ci tarixçi iddia edirdi ki, hər bir qımız bayramından növbəti qımız bayramına qədər ən az kl[i] il, lakin ən çox kr[i] il keçirdi, halbuki hər bir bal bayramından növbəti bal bayramına qədər ən az ml[i] il, lakin ən çox mr[i] il keçirdi.
Hər bir təklif olunan versiyaya bir neçə hökmdarların sülalələrə bölünməsi uyğun gələ bilər. Alimlər razılaşdılar ki, eyni sülalənin nümayəndəsinə hakimiyyətin keçidlərinin sayını şübhəlilik göstəricisi hesab etsinlər.
Proqram yazın ki, heç olmasa bir versiyaya uyğun gələn və ən az şübhəlilik göstəricisinə malik olan bölünməni tapsın və həmçinin ona uyğun olan versiyanı göstərsin.
Giriş məlumatları
Birinci sətirdə n (2 ≤ n ≤ 200000) - salnamədəki bayramların sayı qeyd olunub. Növbəti sətirdə tam ədədlər x[1], x[2], ..., x[n] (1 ≤ x[1] < x[2] < ... < x[n] ≤ 10^9) - bayramların keçirildiyi illər.
Üçüncü sətirdə alimlərin sayı s (1 ≤ s ≤ 50) qeyd olunub. Sonrakı s sətirdə dörd təbii ədəd kl[i], kr[i], ml[i], mr[i] (1 ≤ kl[i] ≤ kr[i] ≤ 10^9), (1 ≤ ml[i] ≤ mr[i] ≤ 10^9) qeyd olunub.
Çıxış məlumatları
Birinci sətirdə p və q ədədləri olmalıdır, burada p - ən az şübhəlilik göstəricisinə malik bölünməyə uyğun gələn alim nömrəsi, q - bu bölünmənin şübhəlilik göstəricisidir.
İkinci sətir n ədəd 1 və 2 rəqəmlərindən ibarət olmalıdır, aralarında boşluq olmadan yazılmış, birinci və ya ikinci sülalənin nümayəndəsinin hakimiyyətə gəlməsini göstərir. Əgər ən az şübhəlilik göstəricisi q olan bir neçə həll varsa, onlardan istənilən birini çıxarın.
Əgər alimlərin heç bir versiyasında bayramlar arasındakı vaxt intervallarına uyğun olaraq sülalələr arasında hakimiyyət dövrlərinin bölünməsi mümkün deyilsə, 0 ədədini çıxarın.