Tämä tehtävä on vuorovaikutteinen. Jokaisen rivin tulostamisen jälkeen sinun tulee tyhjentää tulostuspuskuri (flush). Voit käyttää cout << flush C++:ssa, System.out.flush() Javassa ja sys.stdout.flush() Pythonissa. Sinun on noudatettava tarkasti Vuorovaikutus-osion ohjeita; muuten voit saada tuomioksi väärän vastauksen (wrong answer), aikarajan ylityksen (time limit exceeded) tai muun virheen.

Koska kaikissa tehtävissä päähenkilöinä ovat myyttiset kääpiöt, voi olla vihdoinแarvoista ajatella jotakin konkreettista.

On olemassa piilotettu lukujono $A$, jonka pituus on $N$ ja joka koostuu kokonaisluvuista väliltä $[0, 2^N - 1]$. Tehtävänäsi on selvittää se käyttämällä rajoitettua määrää kyselyitä. Jokaisessa kyselyssä annat pituutta $N$ olevan lukujonon $B$, jonka alkiot ovat väliltä $[0, 2^N - 1]$. Vastaus lasketaan seuraavasti:

• Luodaan lukujono $C$, missä $C$:n $i$-s alkio on lukujonojen $A$ ja $B$ $i$-nsien alkioiden bittikohtainen xor (bitwise xor). Merkitsemme xor-operaatiota symbolilla $\oplus$.
• Muodostetaan joukko $S$ kaikkien niiden arvojen joukkona, jotka voidaan saada ottamalla xor jostakin $C$:n alkioiden osajoukosta. Erityisesti tyhjälle osajoukolle xor on $0$.
• Kyselyn vastaus on $|S|$.

Esimerkiksi jos $A = (1, 4, 3)$ ja $B = (0, 4, 7)$, niin $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ ja $S = \{0, 1, 4, 5\}$, joten vastaus on $4$.

Kahden luvun $x$ ja $y$ bittikohtaisessa xor-tuloksessa bitti $i$ on päällä, jos ja vain jos täsmälleen toisessa luvuista $x$ ja $y$ bitti $i$ on päällä. Esimerkiksi $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$. C++:ssa ja Pythonissa xor on operaattori ^.

Vuorovaikutus

Lukujono $A$ on kiinnitetty alussa eikä se riipu tehdyistä kyselyistä.

Lue ensin rivi, joka sisältää yhden kokonaisluvun $1 \le N \le 60$. Sen jälkeen voit tehdä kyselyitä.

Tehdäksesi kyselyn tulosta rivi, joka sisältää merkin ? ja sen perässä $N$ kokonaislukua väliltä $[0, 2^N - 1]$. Lue vastauksena yksi kokonaisluku, joka on kyselyn vastaus.

Kun olet valmis, tulosta ! ja sen perässä piilotetun lukujonon $N$ kokonaislukua. Tämän jälkeen ohjelmasi tulee päättyä tulostamatta enää mitään.

Muista tyhjentää tulostuspuskuri (flush) jokaisen kyselyn ja vastauksen kirjoittamisen jälkeen. Laita välilyönnit lukujen ja symbolien ?, ! väliin.

Esimerkit

Syöte 1

3
4
8

Tuloste 1

? 1 2 3
? 0 0 0
! 1 3 4

Huomautus

Selitys esimerkkivuorovaikutukselle: $N = 3$ Kysely ? 1 2 3: $B = (1, 2, 3)$, $C = (1 \oplus 1, 3 \oplus 2, 4 \oplus 3) = (0, 1, 7)$, $S = \{0, 1, 6, 7\}$, vastaus on $4$. Kysely ? 0 0 0: $B = (0, 0, 0)$, $C = (1 \oplus 0, 3 \oplus 0, 4 \oplus 0) = (1, 3, 4)$, $S = \{0, 1, \dots, 7\}$, vastaus on $8$. Tuloste ! 1 3 4: Piilotettu lukujono on $A = (1, 3, 4)$.

Paikallinen testaus

Files-osiosta löydät tiedoston B.zip, joka sisältää esimerkkitestit ja tarkistimen grader.cpp. Testataksesi ratkaisuasi käännä se ja anna sitten testin nimi ja suoritettava tiedostosi käännetylle ./grader-ohjelmalle:

./grader [test] [executable]

Esimerkiksi: ./grader 0b.in ./abc

Esimerkkitarkistimen ei taata käyttäytyvän täysin samalla tavalla kuin virallisen tarkistimen. Kumpikaan niistä ei kuitenkaan ole mukautuva (adaptive).