Düzbucaqlılar-2
Dacha sahələrinin çox sayda alınması ilə əlaqədar olaraq, iki böyük, lakin bir o qədər də qürurlu dövlət (şərti olaraq onları "birinci" və "ikinci" adlandıraq) sərhədləri yaxınlığındakı torpaq sahələrinə aid bir sıra razılaşmalar müəyyən etdilər.
Bu yenilikləri daha yaxşı başa düşmək üçün bu dövlətlər arasındakı sərhədi divarda asılmış xəritədə nəzərdən keçirək, burada şimal yuxarıda yerləşir. Koordinat sistemini ortonormal şəkildə təqdim edək, burada OX oxu qərbdən şərqə, OY isə cənubdan şimala yönəldilmişdir. OX oxunda n bərabər ölçülü seqmentləri nəzərdən keçirək, bu seqmentlərin i-ci seqmenti koordinatlara malikdir [i-1, i]. Hər birinə OY oxuna paralel olan və seqmentin özündən keçən bütün mümkün düz xətlərin yaratdığı şaquli zolaq uyğunlaşdırılır. İndi dövlətləri ayırmaq üçün təqdim edilmiş şaquli zolaqlara əsaslanan uydurma səviyyə sistemini nəzərdən keçirək. Hər bir zolaq üçün onun səviyyəsini müəyyən edək, bu səviyyə bəzi z_i ədədi ilə təyin olunur. Müvafiq seqmentin şaquli zolağına aid olan və səviyyədən yuxarıda yerləşən nöqtələr birinci dövlətə, aşağıda yerləşənlər isə ikinci dövlətə aiddir.
Dövlətlərdən birinin yerli sakini koordinat oxlarına paralel tərəfləri olan düzbucaqlı bir torpaq sahəsi almaq istədikdə (başqa növ sahələr heç kəsi maraqlandırmır), bunu edə bilər, əgər onun doğma dövləti seçilmiş sahədə üstünlük təşkil edirsə. Bu, dövlətin OX oxundakı seqmentlərdən yaranan şaquli zolaqların digər dövlətdən daha çox hissəsində üstünlük təşkil etməsi ilə baş verir. Şaquli zolaqlar üçün üstünlük xüsusiyyəti aşağıdakı kimi müəyyən edilir: əgər bir dövlətə aid olan sahənin sahəsi digərinə aid olan sahədən ciddi şəkildə böyükdürsə, birinci dövlət bu zolaqda üstünlük təşkil edir.
Sizdən, sahədə üstünlük təşkil edən dövləti müəyyən edə bilən və dövlətlər arasındakı sərhədi dəyişdirə bilən bir proqram yazmağınızı xahiş edirlər.
Giriş verilənləri
Giriş faylının ilk sətirində n - OX oxunun bölündüyü seqmentlərin sayı (1 ≤ n ≤ 50000) yazılmışdır. İkinci sətirdə dövlətlər arasındakı sərhədi müəyyən edən z_i ədədləri (0 ≤ z_i ≤ 10^9) verilmişdir. Üçüncü sətirdə proqramınıza olan sorğuların sayı m (1 ≤ m ≤ 100000) göstərilmişdir. Sonra m sorğu sətirləri gəlir. Hər bir sorğu "C x z" və ya "Q x_1 y_1 x_2 y_2" formasındadır. "C x z" formasında olan sorğu, x nömrəli şaquli zolağın səviyyəsinin z olduğunu bildirir (1 ≤ x ≤ n, 1 ≤ z ≤ 10^9). "Q x_1 y_1 x_2 y_2" formasında olan sorğu (1 ≤ x_1 ≤ x_2 ≤ n, 0 ≤ y_1 < y_2 ≤ 10^9) isə, sol sərhədi x_1 nömrəli şaquli zolaq (daxil olmaqla), sağ sərhədi isə x_2 nömrəli şaquli zolaq (daxil olmaqla) olan və cənubdan və şimaldan y_1 və y_2 koordinatları ilə məhdudlaşdırılmış sahədə hansı dövlətin üstünlük təşkil etdiyini göstərməlidir. Giriş faylındakı bütün ədədlər tam ədədlərdir.
Çıxış verilənləri
Hər bir "Q x_1 y_1 x_2 y_2" sorğusu üçün, əgər bu sahədə birinci dövlət üstünlük təşkil edirsə 1, ikinci dövlət üstünlük təşkil edirsə 2, və heç bir dövlət üstünlük təşkil etmirsə 0 çıxarın.