8. Inovatívny dážď

Hady sužované neustálymi dažďami dali jedného dňa hlavy dohromady a vynašli Hadí Automat Aktualizujúci Rozbité Počasie. Problém je, že je to iba jednoduchý prototyp, ktorý dokáže jednu vec: vyjasní počasie na nejakom obdĺžnikovom kuse zeme. Následne sa hady znovu zamysleli a dokázali upraviť Hadí Automat Aktualizujúci Rozbité Počasie, aby slnil vo viac neprekrývajúcich sa obdĺžnikoch naraz.

Hady by chceli použiť Automat na oslňovanie parku. Park si vieme predstaviť ako štvorcovú plochu s \(n\) lavičkami a \(n-1\) cestičkami spájajúcimi lavičky. Navyše, cestičky sú postavené tak, že z každej lavičky sa vieme po cestičkách dostať ku ktorejkoľvek inej lavičke (teda cestičky tvoria strom).

Hady väčšinou využívajú park tak, že sa rozležia po nejakej ceste: položia hlavu na jednu lavičku, chvost na druhú lavičku (alebo to môže byť had veľmi krátky a ležiaci len na jednej lavičke) a zvyšok teda na lavičky cestou medzi týmito dvoma lavičkami. Predtým nastavia Automat, aby oslnil niekoľko obdĺžnikov tak, aby oslnil práve tie lavičky kde had leží, ale nie tie prázdne.

Ako sa had ukladá na slnenie, s hrôzou si uvedomí, že si nepamätá, či nastavil Automat správne a bude slniť práve tie lavičky kde had leží. Pomôžte mu!

Úloha

Existuje \(n\) lavičiek pospájaných \(n-1\) cestičkami. Lavičky ležia na štvorcovej ploche rozmerov \(n\times n\).

Postupne prichádza \(q\) hadov. Pre každého hada poznáme lavičku, na ktorej má hlavu, lavičku, na ktorej má chvost a konfiguráciu Automatu. Konfigurácia Automatu pozostáva z niekoľko neprekrývajúcich sa obdĺžnikov, ktoré majú byť slnené. Pre každého hada zistite, či Automat nakonfiguroval správne, teda či obdĺžniky obsahujú práve tie lavičky, na ktorých leží had.

Hady využívajú park v dostatočných odstupoch po sebe, takže sa nemusíte trápiť, či sa hady neprekrývajú alebo neslnia iného hada. Žiadne predchádzajúce nastavenia Automatu neovplyvňujú nadchádzajúce slnenia.

Formát vstupu a výstupu

Na prvom riadku vstupu je číslo \(n\) – počet lavičiek, \(1 \leq n \leq 40\,000\).

Na ďalších \(n\) riadkoch sú súradnice lavičiek. Na \(i\)-tom z nich sú medzerami oddelené celé čísla \(x_i\) a \(y_i\) – súradnice lavičky, \(1 \leq x_i, y_i \leq n\).

Na ďalších \(n-1\) riadkoch je popis cestičiek: pre každú cestičku na samostatnom riadku sú dve čísla oddelené medzerou, \(a\) a \(b\), \(1 \leq a, b \leq n\), \(a \neq b\).

Ďalší riadok obsahuje číslo \(q\) – počet slniacich sa hadov, \(1 \leq q \leq 100\,000\).

Pre každého slniaceho sa hada dostanete najskôr tri čísla oddelené medzerou \(a\), \(b\) a \(k\). \(1 \leq a, b \leq n\) – postupne čísla lavičky kde má had hlavu a lavičky, kde má chvost, a \(1 \leq k \leq 3\) – počet slnených obdĺžnikov. Nasledujúcich \(k\) riadkov obsahuje popis obdĺžnikov: štyri medzerou oddelené čísla \(x_1\), \(y_1\), \(x_2\) a \(y_2\) – súradnice najskôr ľavého dolného a potom pravého horného bodu obdĺžnika. \(x_1\leq x_2\) a \(y_1 \leq y_2\). Platí že bod \((x, y)\) je v tomto obdĺžniku práve ak \(x_1 \leq x \leq x_2\) a \(y_1 \leq y \leq y_2\). Je garantované, že obdĺžniky sa neprekrývajú. To znamená, že neexistuje žiadny bod \((x, y)\), ktorý je v dvoch rôznych obdĺžnikoch.

Pre každého hada vypíšte jeden riadok obsahujúci OK, ak je Automat správne nakonfigurovaný, a NIE ak niečo je zle.

Hodnotenie

Je 8 sád vstupov.

• V prvých troch sadách platí \(1 \leq n, q \leq 1000\)
• V prvej, štvrtej a piatej sade navyše platí, že cestičky vždy spájajú lavičky s číslami \(i\) a \(i + 1\)
• V piatej a šiestej sade navyše platí, že \(k = 1\) pre každého hada
• V siedmej a ôsmej sade neplatia žiadne ďalšie obmedzenia

Neodporúčame pokúšať sa úlohu riešiť v pomalších jazykoch, ako napríklad Python.

Príklad

Input:

9
1 1     // Pozicie laviciek
1 5
3 4
4 1
4 2
5 1
1 6
2 6
1 7
1 2     // Cesticky
1 3
1 4
2 7
4 5
4 6
7 8
7 9
5
1 9 1
1 1 2 7
1 9 1
1 1 1 7
8 3 2
1 3 4 6
1 1 2 2
5 8 3
1 1 4 2
1 3 2 6
5 5 8 9
3 5 1
3 1 4 4

Output:

NIE
OK
OK
OK
NIE

V prvom prípade jediný obdĺžnik slní lavičku číslo 8, čo nechceme. V druhom prípade je rovnaký had, ale zmenšený slnený obdĺžnik. Všimnite si v treťom príklade, že obdĺžnik nemusí pokrývať súvislú časť hada (táto otázka by sa nemohla objaviť v sade 7). V štvrtej otázke máme tretí obdĺžnik úplne zbytočne, – neslní žiadne lavičky. Piaty had zabudol oslniť lavičku 1.

Znaky // označujú komentáre, ktoré sa v skutočnom vstupe neobjavia. Slúžia len na objasnenie vstupu.