Zadanie

Buldog Milionár

Počet bodov: 15, časový limit: 500ms

Šakal sa, ani nevedel ako, ocitol v súťaži o veľké peniaze. Pred ním stojí \(n\) vriec, v každom z nich je buď liter zlata, alebo liter železa. Vrecia sú až na ich obsahy identické. Jediné, čo s nimi vie robiť, je vziať jedno vreco do ľavej ruky, jedno do pravej, a porovnať ich hmotnosti. Samozrejme, diváci sa nebudú pozerať na jeho rozhodovanie desať rokov: stihne spraviť iba \(1\,000\) porovnaní. Potom si jedno vreco vyberie a to bude jeho výhra.

Pretože v škole nedával pozor, nevie, či je zlato ľahšie alebo ťažšie, ako železo. Ich hustoty sú ale určite odlišné. Tiež si je istý, že vriec so zlatom je menej, ako vriec so železom: konkrétne, vriec so zlatom je nanajvýš \(0.45n\).

Šakal si je vedomý toho, že ak by sa mu podarilo si vybrať vrece so zlatom, čakal by ho nemilý osud: pán organizátor by ho obvinil z podvádzania a pomocou svojho vplyvu by zaručil, že by určite Šakal skončil v base. Radšej si teda vezme to vrece železa.

Pomôžte Šakalovi si vybrať vrece so železom.

Vstup a výstup

Toto je interaktívna úloha.

Testovač vám na začiatku pošle riadok obsahujúci jedno číslo \(n\): počet vriec. Platí \(10 \leq n \leq 100\,000\).

Následne testovaču hovoríte, ktoré dve vrecia chcete porovnať. Správy, ktoré mu posielate, musia mať nasledovný formát: \(0\ a\ b\), kde \(a, b\) sú čísla vriec. Vrecia číslujeme \(1, 2, \ldots, n\). Nezabudnite flushovať, aby sa vaša odpoveď skutočne testovaču odoslala.

Testovač vám na oplátku hovorí, či ich hmotnosť je rovnaká alebo rôzna. Pošle vám riadok obsahujúci v prvom prípade \(0\), inak \(1\).

Nakoniec musíte testovaču oznámiť (nanajvýš po \(1\,000\) porovnaniach), ktoré vrece si vyberáte. To spravíte správou vo formáte \(1\ c\), kde \(c\) je číslo vybraného vreca.

Ak sa testovaču vaše výstupy nepáčia, môže okamžite komunikáciu ukončiť. V takom prípade by ste to mali vedieť detekovať a tiež skončiť, v opačnom prípade sa totiž budete snažiť čítať/zapisovať tam, kde to nejde, a váš program skončí s Chyba počas behu programu namiesto Zlá odpoveď.

Príklad

5
> 0 1 2
0
> 0 2 3
0
> 0 3 4
0
> 0 4 5
0
> 1 1

V tomto príklade všetky vrecia obsahujú železo. (Kto povedal, že súťaž musí byť fér?)

5
> 0 1 2
1
> 0 2 3
1
> 0 3 4
1
> 0 4 5
1
> 1 3

Jeden kov je vo vreciach \(1, 3, 5\), druhý kov je vo vreciach \(2, 4\). Pretože železo je vždy častejší kov, prvý spomínaný kov je železo.