8. Oporné múry

Bude raz jeden dom. V tom dome bude bývať Samko. Keď ho postavia. A za tým domom bude kopec. Ten kopec tam dokonca je už teraz. A je to strmý kopec. A ako to už so strmými kopcami býva, vždy je pri ňom riziko zosuvu pôdy. Samkovi by sa, samozrejme, takýto zosuv nepáčil (keďže by mu mohol poškodiť jeho dom). Preto sa rozhodol (ešte pred stavbou svojho domu) postaviť na svahu niekoľko oporných múrov, ktoré svah spevnia a zosuvom zabránia.

Nechal si urobiť geodetický prieskum kopca, dlho nad ním hútal a nakoniec naplánoval niekoľko múrov. Každý z týchto múrov bude vodorovný – pôjde po vrstevnici. Naplánované múry môžu mať rôzne dĺžky (nemusia byť na celú šírku svahu) a môžu byť v rôznych výškach (na rôznych vrstevniciach).

Plný entuziazmu si Samko naplánoval, v akom poradí jednotlivé múry postaví. Ešte v tom istom záchvate entuziazmu si tento plán nechal schváliť na stavebnom úrade. Neskôr, keď nadšenie trochu opadlo, si však uvedomil, že toto poradie možno nie je najšťastnejšie. Pri stavbe múru v strmom svahu sa vám totiž môže občas stať, že sa vám nejaký ten betónový kváder vymkne spod kontroly a skotúľa sa dolu kopcom. To je už samo o sebe trochu nepríjemné, oveľa horšie však je, ak cestou narazí na nejaký iný, už postavený múr (snáď netreba vysvetľovať prečo).

Samko má už plán stavby schválený na úrade a nemôže sa len tak rozhodnúť, že múry postaví v inom poradí. Môžete mu však aspoň povedať, pri stavbe ktorých múrov hrozí, že by mu uvoľnený kus betónu poškodil nejaký nižšie položený, skôr postavený múr. Pri týchto múroch si potom bude na svoje betónové kvádre dávať špeciálny pozor.

Úloha

Pre účely tejto úlohy si svah budeme predstavovať ako naklonenú rovinu (uhol naklonenia nie je podstatný). Na popisovanie miest na svahu si zavedieme nasledovnú súradnicovú sústavu: vrstevnica tvoriaca úpätie svahu bude \(x\)-ová os a jedna zo spádnic bude \(y\)-ová os, pričom \(y\)-ová súradnica bude rásť s rastúcou nadmorskou výškou. Múry teda budú v našom súradnicovom systéme zodpovedať úsečkám rovnobežným s \(x\)-ovou osou.

Hovoríme, že múr \(A\) ohrozuje múr \(B\), ak je možné z nejakej časti múru \(A\) pustiť kameň tak, aby sa skotúľal a narazil do múru \(B\) (pričom kamene sa kotúľajú po spádniciach). Formálne, múr \(A\) ohrozuje múr \(B\), ak je na vyššej \(y\)-ovej súradnici ako múr \(B\) a ich kolmé projekcie na os \(x\) majú prienik kladnej dĺžky (prienik v jednom bode teda nestačí).

Dostanete popis jednotlivých múrov a poradie, v akom ich Samko bude stavať. O múre \(C\) povieme, že je riskantný, ak existuje nejaký múr \(D\) taký, že \(C\) ohrozuje \(D\), ale múr \(D\) bude postavený skôr než múr \(C\). Pre každý múr rozhodnite, či je riskantný, alebo nie.

Formát vstupu

Prvý riadok vstupu obsahuje jedno celé číslo \(n\) (\(1 \leq n \leq 100\,000\)) – počet múrov. Nasleduje \(n\) riadkov, každý z nich popisuje jeden múr. Popis jedného múru sa skladá z troch medzerami oddelených celých čísel \(x_{i,1}\), \(x_{i,2}\), \(y_i\), ktoré znamenajú, že daný múr je úsečka s koncovými bodmi \((x_{i,1},y_i)\) a \((x_{i,2}, y_i)\). Pri každom múre bude pre tieto čísla platiť \(-10^9 \leq x_{i,1} < x_{i,2} \leq 10^9\) a \(0 \leq y_i \leq 10^9\). Navyše platí, že všetky múry sú navzájom disjunktné. Inými slovami, žiadne dva múry nemajú spoločný bod.

Múry si očíslujme \(1, 2, \dots, n\) v poradí, v akom sú uvedené na vstupe. Posledný riadok vstupu obsahuje medzerami oddelené čísla múrov v poradí, v akom ich Samko bude stavať. Každé z čísel \(1, 2, \dots, n\) sa v poslednom riadku vstupu vyskytne práve raz.

Formát výstupu

Pre každý múr (v poradí, ako sú očíslované) vypíšte jeden riadok obsahujúci slovo ANO ak je daný múr riskantný, resp. NIE, ak nie je riskantný.

Príklady

Input:

5
1 6 1
6 9 6
-1 2 4
5 8 3
3 6 4
5 1 3 2 4

Output:

NIE
NIE
ANO
ANO
NIE

Po postavení všetkých múrov bude svah vyzerať nasledovne:

Múry budú postupne pribúdať takto:

Stavba múrov č. 5 a 1 bude bez rizika. Pri stavbe múru č. 3 hrozí poškodenie múru 1. Následná stavba múru č. 2 je opäť bez rizika. Nakoniec, pri stavbe múru 4 hrozí poškodenie múru 1. Riskantné sú teda múry č. 3 a 4.