Diese Aufgabe ist interaktiv. Nach der Ausgabe jeder Zeile musst du den Ausgabepuffer leeren (flush). Du kannst cout << flush in C++, System.out.flush() in Java und sys.stdout.flush() in Python verwenden. Du musst die Anweisungen im Abschnitt Interaktion strikt befolgen; andernfalls erhältst du möglicherweise Bewertungen wie falsche Antwort (wrong answer), Zeitlimit überschritten (time limit exceeded) oder andere.

Da in allen Aufgaben mythische Zwerge die Hauptfiguren sind, lohnt es sich vielleicht, endlich einmal über etwas Greifbares nachzudenken.

Es gibt eine versteckte Folge $A$ der Länge $N$, die aus ganzen Zahlen im Bereich $[0, 2^N - 1]$ besteht. Deine Aufgabe ist es, sie mithilfe einer begrenzten Anzahl von Anfragen wiederherzustellen. In jeder Anfrage gibst du eine Folge $B$ der Länge $N$ mit Elementen im Bereich $[0, 2^N - 1]$ an. Die Antwort wird wie folgt berechnet:

• Es wird eine Folge $C$ erstellt, wobei das $i$-te Element von $C$ das bitweise XOR (bitwise xor) der $i$-ten Elemente von $A$ und $B$ ist. Wir bezeichnen XOR mit $\oplus$.
• Die Menge $S$ wird als die Menge aller Werte konstruiert, die man durch XOR-Verknüpfung einer Teilmenge von Elementen aus $C$ erhalten kann. Insbesondere ist für die leere Teilmenge das XOR gleich $0$.
• Die Antwort auf die Anfrage ist $|S|$.

Wenn zum Beispiel $A = (1, 4, 3)$ und $B = (0, 4, 7)$ ist, dann ist $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ und $S = \{0, 1, 4, 5\}$, also lautet die Antwort $4$.

Das bitweise XOR zweier Zahlen $x$ und $y$ hat das Bit $i$ genau dann gesetzt, wenn genau eine der Zahlen $x$ und $y$ das Bit $i$ gesetzt hat. Zum Beispiel ist $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$. In C++ und Python ist XOR der Operator ^.

Interaktion

Die Folge $A$ steht von Anfang an fest und hängt nicht von den gestellten Anfragen ab.

Lies zuerst eine Zeile mit einer ganzen Zahl $1 \le N \le 60$ ein. Danach kannst du Anfragen stellen.

Um eine Anfrage zu stellen, gib eine Zeile mit ? gefolgt von $N$ ganzen Zahlen im Bereich $[0, 2^N - 1]$ aus. Lies als Antwort eine ganze Zahl ein, die das Ergebnis darstellt.

Wenn du bereit bist, gib ! gefolgt von den $N$ ganzen Zahlen der versteckten Folge aus. Danach muss sich dein Programm ohne weitere Ausgabe beenden.

Denke daran, die Ausgabe nach jeder Anfrage und nach dem Schreiben der Antwort zu leeren (flush). Setze Leerzeichen zwischen Zahlen und den Symbolen ?, !.

Beispiele

Eingabe 1

3
4
8

Ausgabe 1

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

Hinweis

Die Erklärung für die Beispielinteraktion: $N = 3$ Anfrage ? 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\}$, Antwort ist $4$. Anfrage ? 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\}$, Antwort ist $8$. Ausgabe ! 1 3 4: Die versteckte Folge ist $A = (1, 3, 4)$.

Lokales Testen

Im Abschnitt Files findest du B.zip mit Beispieltests und einem Grader grader.cpp. Um deine Lösung zu testen, kompiliere sie und übergib dann den Testnamen und deine ausführbare Datei an den kompilierten ./grader:

./grader [test] [executable]

Zum Beispiel: ./grader 0b.in ./abc

Es wird nicht garantiert, dass sich der Beispiel-Grader identisch zum offiziellen verhält. Allerdings ist keiner von beiden adaptiv.