Dostlar

Aminin $n$ sayda dostu onun ad gününü qeyd etmək üçün evinə toplanıb. Onlar bir cərgədə dayanıb Aminin şəninə sağlıq deyirlər. Gəlin onları bu cərgə boyunca $1$-dən $n$-ə nömrələyək.

Bu dostlar arasında bir-birini tanıyanlar və tanımayanlar var. Aminin dostlarının oxuduğu orta məktəb $(a_i)$ və universitet $(b_i)$ verilir. Əgər iki nəfərin həm oxuduğu orta məktəb həm də universitet fərqlidirsə, onlar bir-birini tanımır. Riyazi olaraq ifadə etsək, Aminin $i$-ci və $j$-ci dostu bir-birini o halda tanımır ki, $a_i\ne a_j$ və $b_i\ne b_j$ şərti ödənir.

Amin isə ad günü olmasına baxmayaraq yenə də qəribə sorğular düşünür. “Görəsən cərgədə $l$-ci dostumdan $r$-ci dostuma kimi ($l$ və $r$ daxil) olan hissədə bir-birini tanımayan hər hansı iki dostum varmı? 🤔”

Aminin ağlından keçən sorğulara cavab verin.

Giriş verilənləri

Birinci sətirdə bir tam ədəd $n(2\le n\le 10^5)$, növbəti $n$ sətrin hər birində isə iki tam ədəd $a_i$ və $b_i(1\le a_i,b_i\le 10^9,1\le i\le n)$ verilir. Növbəti sətirdə Aminin ağlından keçən sorğuların sayı, $q(1\le q\le 10^5)$ verilir. Növbəti $q$ sətrin hər birində soruğular, yəni iki tam ədəd $l_j$ və $r_j(1\le l_j<r_j\le n)$ verilir.

Çıxış verilənləri

Çıxışa hər sorğu üçün yeni sətirdən iki tam ədəd, verilmiş aralıqda Aminin bir-birini tanımayan hər hansı iki dostunun nömrəsini, əgər belə iki nəfər yoxdursa $00$ verin. Bir neçə düzgün cavab olarsa, onlardan hər hansı birini çıxışa verə bilərsiniz.

Nümunələr

Qiymətləndirmə

Bu məsələ aşağıdakı kimi $4$ alt tapşırıqdan ibarətdir. Alt tapşırıq üçün ballar yalnız bu alt tapşırığa aid bütün testlər uğurla keçdikdə verilir.

1. ($20$ bal): $n,q\le 100$;

2. ($30$ bal): $n,q\le 1000$;

3. ($20$ bal): $n,q\le 5000$;

4. ($30$ bal): $Əlavəməhdudiyyətyoxdur$;