Vandal

Nakon što je njegov Chelsea izgubio od Real Madrida, Ivan odluči vandalizirati Marinovo stablo. Marin u svom dvorištu ima potpuno binarno stablo koje ima N listova. U najlijevijem listu upisan je broj 1, u drugom najlijevijem broj 2, itd. U čvorovima koji nisu listovi nije upisan niti jedan broj.

Slika 1: stablo na početku.

Slika 2: stablo nakon operacije.

Ivan vandalizira Marinovo stablo nizom operacija. U jednoj operaciji on odabere neki čvor koji nije list te zamjeni njegovo lijevo i desno dijete, tj. ono dijete koje je do sada bilo lijevo, nakon operacije je desno, a ono koje je bilo desno, nakon operacije je lijevo. Na drugoj slici možete vidjeti kako izgleda početno stablo nakon što je Ivan svoju operaciju izvršio nad korijenom stabla. Nakon što je izvršio jako puno operacija, Ivan otiđe do Marina te mu prizna vandaliziranje stabla. Marin, sav izbezumljen, ga pita kako sada izgleda njegovo stablo. "Neću ti reći. Možeš me pitati najviše Q pitanja oblika: Nalazi li se u a-tom listu s lijeva broj b? pa možda tako saznaš." Marin bi htio čim prije saznati kako izgleda njegovo stablo pa moli Vas za pomoć.

Interakcija

Prije interakcije s Ivanom, potrebno je učitati prirodne brojeve N i Q. Nakon učitavanja brojeva N i Q moguće je postavljati pitanja oblika "? a b" na standardan izlaz. Mora vrijediti 1 ≤ a, b ≤ N . Nakon svakog upita na standardni ulaz dobivate cijeli broj x koji je jednak 1 ako je Ivanov odgovor na pitanje DA ili 0 ako je njegov odgovor na pitanje NE. Nakon svakog izdanog upita obavezno napravite flush izlaza, te pročitajte odgovor sa standardnog ulaza. Ukupni broj upita ne smije biti veći od Q. Kada odredite kako izgleda Marinovo stablo, ispišite “! p1 p2 . . . pn ” na standardni izlaz, gdje pi označava broj koji je zapisan u i-tom listu s lijeva u Marinovom stablu. Zatim napravite flush izlaza, te završite izvođenje svog programa. Napomena: Za flush izlaza u C++-u možete koristiti fflush(stdout) ili cout « flush, a u Python-u stdout.flush().

Bodovanje

Podzadatak Bodovi Ograničenja

1 4 1 ≤ N ≤ 4, Q = 16 2 7 1 ≤ N ≤ 128, Q = 8128 3 14 1 ≤ N ≤ 128, Q = 896 4 25 1 ≤ N ≤ 128, Q = 448

Primjer interakcije

U probnom su primjeru u listovima s lijeva na desno upisani brojevi 2, 1, 3 i 4. Izlaz Ulaz Napomena 4 10 Unosimo broj listova N = 4 i maksimalni dopušteni broj pitanja Q. ? 1 1 0 U prvom listu s lijeva ne nalazi se broj 1. ? 1 2 1 U prvom listu s lijeva se nalazi broj 2. ? 2 1 1 U drugom listu s lijeva se nalazi broj 1. ? 3 3 1 U trećem listu s lijeva se nalazi broj 3. ? 3 4 1 U četvrtom listu s lijeva se nalazi broj 4. ! 2 1 3 4 Zaključujemo da u prvom listu s lijeva piše broj 2, u drugom 1, u trećem 3 i u četvrtom 4.