Düzbucaqlılar-2#1480
Şəhərətrafı torpaq sahələrinin çoxlu alışı səbəbindən iki böyük və qürurlu dövlət (onları "birinci" və "ikinci" adlandıraq) sərhədlərinin yaxınlığında torpaq sahələri ilə bağlı bir sıra razılaşmalar əldə ediblər.
Bu razılaşmaları daha yaxşı anlamaq üçün xəritədə bu dövlətlərin sərhədini divarda asılmış şəkildə təsəvvür edin, şimal yuxarıda olsun. Ortonormal koordinat sistemi istifadə edək, burada OX oxu qərbdən şərqə, OY oxu isə cənubdan şimala istiqamətlənib.
OX oxunu bərabər hissəyə bölün. -ci seqmentin koordinatları [i-1, i] olur. Hər bir belə seqmentlə, bu seqmentdən keçən və OY oxuna paralel olan bütün mümkün düz xətlərin təşkil etdiyi şaquli zolaq əlaqələndirilir. Hər bir zolaq üçün tam ədəd olan bir səviyyə z_i təyin olunur. -ci seqmentin zolağında səviyyə z_i-dən yuxarı olan nöqtələr birinci dövlətə, z_i-dən aşağı olan nöqtələr isə ikinci dövlətə məxsusdur.
Əgər dövlətlərin vətəndaşı tərəflərə paralel tərəfləri olan düzbucaqlı torpaq sahəsi almaq istəyirsə, bunu yalnız doğma dövləti seçilmiş sahədə üstünlük təşkil edirsə edə bilər. Bu, əgər müvafiq seqmentlərə uyğun gələn şaquli zolaqlarda onun dövləti digər dövlətdən daha çox zolaqda üstünlük təşkil edirsə baş verir. Bir zolaqda dövlət üstünlük təşkil edir, əgər ondan həmin zolaqda ona məxsus sahə digərinə məxsus sahədən ciddi şəkildə artıqdır.
Verilmiş bölgə üçün tələb olunan region üzrə üstünlük təşkil edən dövləti müəyyən edən və sərhəddi dəyişdirməyə imkan verən proqram yazın.
Birinci sətirdə (1 \leq n \leq 50000) — OX oxunun neçə seqmentə bölündüyü verilir.
İkinci sətirdə sərhəd səviyyələrini müəyyən edən ədəd z_i (0 \leq z_i \leq 10^9) verilir.
Üçüncü sətirdə (1 \leq m \leq 100000) — sorğuların sayı verilir.
Sonrakı sətirin hər birində iki formatdan birində sorğu verilir:
- "C x z": nömrəli zolağın səviyyəsini -yə təyin et (1 \leq x \leq n, 1 \leq z \leq 10^9). - "Q x_1 y_1 x_2 y_2": x_1-dən x_2-yə qədər olan zolaqlar və y_1-dən y_2-yə qədər olan şaquli intervallar üçün (1 \leq x_1 \leq x_2 \leq n, 0 \leq y_1 < y_2 \leq 10^9), hansı dövlətin üstünlük təşkil etdiyini müəyyən et.
Bütün verilən ədədlər tam ədədlərdir.
"Q x_1 y_1 x_2 y_2" formatlı hər sorğu üçün, əgər bu bölgədə birinci dövlət üstünlük təşkil edirsə, ; ikinci dövlət üstünlük təşkil edirsə, ; heç biri üstünlük təşkil etmirsə, çap edin.
Nümunə 1