Ce problème est interactif. Après avoir affiché chaque ligne, vous devez vider le tampon de sortie (flush). Vous pouvez utiliser cout << flush en C++, System.out.flush() en Java et sys.stdout.flush() en Python. Vous devez suivre strictement les instructions de la section Interaction ; sinon, vous risquez de recevoir des verdicts tels que réponse erronée (wrong answer), limite de temps dépassée (time limit exceeded) ou autres.

Puisque toutes les tâches ont des nains mythiques comme personnages principaux, il vaut peut-être enfin la peine de penser à quelque chose de concret.

Il existe une séquence cachée $A$ de longueur $N$ composée d'entiers dans l'intervalle $[0, 2^N - 1]$. Votre tâche consiste à la récupérer en utilisant un nombre limité de requêtes. Dans chaque requête, vous fournissez une séquence $B$ de longueur $N$ avec des éléments dans l'intervalle $[0, 2^N - 1]$. La réponse est calculée comme suit :

• La séquence $C$ est créée où le $i$-ème élément de $C$ est le ou exclusif bit à bit (bitwise xor) des $i$-èmes éléments de $A$ et $B$. Nous notons le ou exclusif par $\oplus$.
• L'ensemble $S$ est construit comme l'ensemble de toutes les valeurs pouvant être obtenues en effectuant le ou exclusif d'un sous-ensemble d'éléments de $C$. En particulier, pour le sous-ensemble vide, le ou exclusif vaut $0$.
• La réponse à la requête est $|S|$.

Par exemple, si $A = (1, 4, 3)$ et $B = (0, 4, 7)$, alors $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ et $S = \{0, 1, 4, 5\}$, donc la réponse est $4$.

Le ou exclusif bit à bit de deux nombres $x$ et $y$ a le bit $i$ activé si et seulement si exactement l'un de $x$ et $y$ a le bit $i$ activé. Par exemple, $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$. En C++ et Python, le ou exclusif est l'opérateur ^.

Interaction

La séquence $A$ est fixée au début et ne dépend pas des requêtes effectuées.

Tout d'abord, lisez une ligne contenant un entier $1 \le N \le 60$. Ensuite, vous pouvez poser des requêtes.

Pour poser une requête, affichez une ligne contenant ? suivi de $N$ entiers dans l'intervalle $[0, 2^N - 1]$. En réponse, lisez un entier qui est la réponse.

Lorsque vous êtes prêt, affichez ! suivi des $N$ entiers de la séquence cachée. Ensuite, votre programme doit se terminer sans autre sortie.

N'oubliez pas de vider la sortie (flush) après chaque requête et après avoir écrit la réponse. Mettez des espaces entre les nombres et les symboles ?, !.

Exemples

Entrée 1

3
4
8

Sortie 1

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

Note

L'explication de l'interaction d'exemple : $N = 3$ Requête ? 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\}$, la réponse est $4$. Requête ? 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\}$, la réponse est $8$. Sortie ! 1 3 4 : La séquence cachée est $A = (1, 3, 4)$.

Tests locaux

Dans la section Files, vous trouverez B.zip contenant des tests d'exemple et un évaluateur grader.cpp. Pour tester votre solution, compilez-la, puis passez le nom du test et votre exécutable au ./grader compilé :

./grader [test] [executable]

Par exemple : ./grader 0b.in ./abc

L'évaluateur d'exemple n'est pas garanti de se comporter de manière identique à l'officiel. Cependant, aucun des deux n'est adaptatif.