Denne oppgaven er interaktiv. Etter å ha skrevet ut hver linje må du tømme utdatabufferen (flush). Du kan bruke cout << flush i C++, System.out.flush() i Java og sys.stdout.flush() i Python. Du må følge instruksjonene i delen Interaksjon strengt; ellers kan du få dommer som feil svar (wrong answer), tidsgrense overskredet (time limit exceeded) eller andre.

Siden alle oppgavene har mytiske dverger som hovedpersoner, kan det være verdt å endelig tenke på noe håndgripelig.

Det finnes en skjult sekvens $A$ av lengde $N$ som består av heltall i intervallet $[0, 2^N - 1]$. Din oppgave er å gjenopprette den ved hjelp av et begrenset antall spørringer. I hver spørring oppgir du en sekvens $B$ av lengde $N$ med elementer i intervallet $[0, 2^N - 1]$. Svaret beregnes som følger:

• Sekvensen $C$ opprettes der det $i$-te elementet i $C$ er bitvis xor (bitwise xor) av de $i$-te elementene i $A$ og $B$. Vi betegner xor med $\oplus$.
• Mengden $S$ konstrueres som mengden av alle verdier som kan oppnås ved å ta xor av en delmengde av elementene i $C$. Spesielt er xor for den tomme delmengden lik $0$.
• Svaret på spørringen er $|S|$.

For eksempel, hvis $A = (1, 4, 3)$ og $B = (0, 4, 7)$, så er $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ og $S = \{0, 1, 4, 5\}$, så svaret er $4$.

Bitvis xor av to tall $x$ og $y$ har bit $i$ satt hvis og bare hvis nøyaktig ett av $x$ og $y$ har bit $i$ satt. For eksempel er $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$. I C++ og Python er xor operatoren ^.

Interaksjon

Sekvensen $A$ er fastsatt fra starten og avhenger ikke av spørringene som gjøres.

Les først en linje som inneholder ett heltall $1 \le N \le 60$. Deretter kan du stille spørringer.

For å stille en spørring, skriv ut en linje som inneholder ? etterfulgt av $N$ heltall i intervallet $[0, 2^N - 1]$. Som svar leser du ett heltall som er svaret.

Når du er klar, skriv ut ! etterfulgt av de $N$ heltallene i den skjulte sekvensen. Deretter skal programmet ditt avsluttes uten ytterligere utskrift.

Husk å tømme utdatabufferen (flush) etter hver spørring og etter å ha skrevet svaret. Sett mellomrom mellom tall og symbolene ?, !.

Eksempler

Inndata 1

3
4
8

Utdata 1

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

Forklaring

Forklaringen på eksempelinteraksjonen: $N = 3$ Spørring ? 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\}$, svaret er $4$. Spørring ? 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\}$, svaret er $8$. Utdata ! 1 3 4: Den skjulte sekvensen er $A = (1, 3, 4)$.

Lokal testing

I delen Files finner du B.zip som inneholder eksempeltester og en grader grader.cpp. For å teste løsningen din, kompiler den, og send deretter testnavnet og den kjørbare filen din til den kompilerte ./grader:

./grader [test] [executable]

For eksempel: ./grader 0b.in ./abc

Eksempelgraderen er ikke garantert å oppføre seg identisk med den offisielle. Ingen av dem er imidlertid adaptive.