Takahaši je zamislio permutaciju dužine ~N~ i ne želi nikome da je kaže. Kako Akina ne voli tajne odlučila je da sazna barem nesto o Takahašijevoj permutaciji. Akina je uspela da ubedi Takahašija da joj najviše ~\lceil \frac{3N}{2} \rceil~ puta odgovori na pitanje oblika "Da li je element na poziciji ~i~ manji od elementa na poziciji ~j~". Akina će biti srećna ako sazna gde se u permutaciji nalaze brojevi ~1~ i ~N~. Pomozite Akini tako što ćete postavljati pitanja umesto nje i pronaći gde se nalaze ~1~ i ~N~.

Opis interakcije

• Na početku učitati broj ~N~ (~3 \leq N \leq 1000~) sa standardnog ulaza.
• Pitanja postavljate tako što na standardni izlaz ispišete "\(0 \space i \space j\)" (bez navodnika) i zatim flush-ujete output. Treba da važi ~1 \leq i,j \leq N~.
• Nakon toga učitajte jednu reč ~O~ koja je odgovor na pitanje. ~O=~"DA" (bez navodnika) ako je element na poziciji ~i~ manji od elementa na poziciji ~j~. U suprotnom ~O=~"NE" (bez navodnika).
• Kada odredite na kojim pozicijama se nalaze brojevi ~1~ i ~N~ ispišite "\(1 \space i \space j\)" na standardni izlaz i flush-ujte output. ~i~ treba da bude pozicija broja ~1~, a ~j~ pozicija broja ~N~ u permutaciji.
• Nakon što postavite pitanje ne zaboravite da ispišete novi red i flush-ujete output.
• U programskom jeziku C++ to možete uraditi sa fflush(stdout) ili cout.flush().
• U programskom jeziku Java koristite System.out.flush().
• U programskom jeziku Python koristite stdout.flush().

Primer interakcije

• Neka je zamišljena permutacija ~P=[2,3,1]~.
• Vaš program prvo učitava broj ~N=3~ sa standardnog ulaza.
• Pretpostavimo da je prvo postavljeno pitanje "\(0 \space 1 \space 2\)". Odgovor je "DA" jer je ~P_1<P_2~.
• Neka je sledeće pitanje "\(0 \space 2 \space 3\)". Odgovor je "NE" jer je ~P_2>P_3~.
• I neka je poslednje postavljeno pitanje "\(0 \space 1 \space 3\)". Odgovor je "NE" jer je ~P_1>P_3~.
• Sada znamo da je ~P_3~ manje od ~P_1~ i ~P_2~ pa je je ~P_3=1~ i kako je ~P_2>P_1~, ~P_2=N~.
• Program sada treba da ispiše "\(1 \space 3 \space 2\)".
• Broj postavljenih upita je ~3~ što je manje od ~\lceil \frac{3N}{2} \rceil = 5~.

Primer ulaza

3
DA
NE
NE

Primer izlaza

0 1 2
0 2 3
0 1 3
1 3 2