Safari Park
Heç safari parkında olmusunuzmu? Bu, heyvanların qəfəsdə saxlanmadığı zoopark kimi bir yerdir. Ziyarətçilər safariyə maşınla və ya piyada gedə bilər və sərbəst heyvanları müşahidə edə bilərlər. Hətta bəzən aslan, pələng kimi təhlükəli heyvanlar da sərbəst saxlanılır. Mən də öz safari parkımı açmışam. Burada heyvanlar müxtəlif bölgələrdə yaşayır. Bir heyvanın bölgəsi təhlükəsizlik məqsədilə digər heyvanın bölgələri ilə kəsişmir. Lakin iki bölgə eyni sərhədə malik ola bilər, baxmayaraq ki, hər hansı digər sərhədin künc nöqtəsində olmaq icazə verilmir. Heyvanlar öz ərazilərini tərk etməmək üçün öyrədilib. İndi safari park o qədər böyükdür ki, tək bir xəritə bütün yeri göstərə bilmir. Beləliklə, insanların maraqlandıqları yerləri tapmalarına kömək etmək üçün bir cihaz hazırlamağa qərar verdim. Lakin cihazın qiymətini azaltmaq üçün ucuz birini aldım. Onların yaddaşı olduqca azdır. İşləri daha az mürəkkəb və emal baxımından səmərəli etmək üçün bütün bölgələri üçbucaq etdik. Amma bu hamısı deyil. Bütün bölgələr əvvəlcədən yüklənməyəcək. Bölgələr ziyarətçinin yerinə görə yüklənəcək. Ziyarətçi monorayla bir yerdən başqa bir yerə parkı ziyarət edə bilər. Beləliklə, üçbucaqlar cihazda müxtəlif yerlərdə görünə bilər. Cihaz o qədər də inkişaf etmiş olmadığı üçün bölgələri göstərə bilər, lakin heç bir etiket göstərmir. Bir şəxs bir nöqtənin koordinatını mətn qutusuna daxil etməli və cihaz həmin bölgənin etiketini xəbərdarlıq mesajında göstərəcək. İki xüsusi etiket var. **0** hər hansı bir bölgədən kənarda olduğunu göstərir, **-1** isə sərhəddə / küncdə olduğunu göstərir.
Məsələn, hazırda iki bölgə haqqında məlumatımız olduğunu fərz edək: Zürafə: **(0, 0)**, **(0, 5)**, **(5, 0)** və Delfin: **(10, 10)**, **(10, 5)**, **(5, 10)**. İndi sorğu koordinatı: **(1, 1)** olarsa, Zürafə göstərəcək. Əgər sorğu **(9, 9)** üçün olarsa, cavab Delfin olacaq. Lakin əgər sorğu: **(5, 5)** olarsa, **0** göstərəcək. İndi xəritədə yeni bir bölgə meydana gəldiyini fərz edək: Aslan: **(4, 6)**, **(6, 4)**, **(4, 4)**. İndi yenidən sorğu **(5, 5)** olarsa, cavab **-1** olacaq.
Beləliklə, ümumiləşdirsək, sizə bəzi üçbucaqlar veriləcək. Üçbucaq tərəfi və həmçinin küncləri paylaşa bilər, lakin heç bir üçbucaq digər üçbucağın hər hansı bir tərəfinin üzərində künc nöqtəsinə malik olmayacaq, yəni müxtəlif üçbucaqların tərəfləri eyni ola bilər, lakin qismən üst-üstə düşməyəcək. Aşağıdakı diaqramı aydınlıq üçün yoxlaya bilərsiniz:
İki üçbucaq ümumi bölgəyə malik olmayacaq. Əgər sorğu nöqtəsi hər hansı bir bölgənin daxilindədirsə, onun etiketini çap etməlisiniz, əgər bütün bölgələrdən kənardadırsa, **0** çap etməlisiniz və əgər hər hansı bir sərhəddə / küncdədirsə, **-1** çap etməlisiniz. Giriş və çıxışın detalları müvafiq bölmədə tapıla bilər.
Giriş verilənləri
Test faylının ilk sətri müsbət tam ədəd **T** (**T** ≤ **2**) ehtiva edir ki, bu da test halların sayını göstərir. Hər bir halın ilk sətri **N** (**N** ≤ **300000**) ehtiva edir ki, bu da əmrlərin sayını göstərir. Hər bir əmr **Q** və ya **R** ilə başlayacaq. **Q** sorğu, **R** isə bölgə deməkdir. **Q** **2** tam ədədlə davam edəcək: **x_q** və **y_q**. **R** **6** tam ədədlə davam edəcək: **x_1 y_1 x_2 y_2 x_3 y_3**. Sizə verilən koordinatların real koordinat olmadığını fərz edə bilərsiniz. Verilən koordinatları son sorğunun cavabından istifadə edərək dekod etməlisiniz. Fərz edək ki, **d** son **Q** sorğusunun cavabıdır (Əvvəlcə **d = 0**), onda verilən koordinatın real koordinatı **x**, **y** olacaq: **x + x_1[d]**, **y + y_1[d]**. Burada, **x_1[d]**, **y_1[d]** **d**’ci bölgənin (dekod edilmiş) ilk koordinatıdır. **d**’ci bölgə **d**’ci **R** əmri ilə təmin edilən bölgədir.
Lakin, əgər **d = 0** və ya **-1** (bölgədən kənarda və ya sərhəddə/ küncdə olduğu halda) **x_1[d] = y_1[d] = 0** qəbul etməlisiniz. Sorğu yalnız müvafiq **Q** əmri əvvəlində təmin edilən bölgələri nəzərə alaraq cavablandırılmalıdır. Əgər bir **Q** əmri əvvəlində **n R** əmri varsa, onda bu əmrin cavabı **-1** ilə **n** arasında olacaq, sərhəddə/küncdə **-1**, hər hansı bir bölgədən kənarda **0** və nöqtənin daxilində olduğu bölgəyə görə digər nömrə olacaq. Bölgələrin koordinatlarının həmişə saat əqrəbi istiqamətində olacağını fərz edə bilərsiniz. Bölgələrin tamamilə təsadüfi qaydada meydana çıxacağını fərz edə bilərsiniz, baxmayaraq ki, bölgələr özləri təsadüfi olmaya bilər. Dekod edilmiş **x y** koordinatlarının dəyəri mənfi olmayacaq və **100000** ilə məhdudlaşdırılacaq.
Çıxış verilənləri
Hər bir test halı üçün əvvəlcə hal nömrəsini çap edin. Beləliklə, hər bir **Q** əmri üçün sorğunun cavabını çap edin. Test halları arasında heç bir boş sətir çap etməyin. Nümunə giriş-çıxışa uyğun olaraq detalları izləyin.