C'est un problème interactif. Pensez à vider le tampon de sortie après chaque affichage. Pour cela, vous pouvez utiliser :

• fflush(stdout) ou cout.flush() en C/C++ ;
• System.out.flush() en Java et Kotlin ;
• sys.stdout.flush() en Python ;
• Consultez la documentation pour les autres langages.

Little Cyan Fish possède une permutation secrète $p_0,p_1,\ldots,p_n$ de longueur $n+1$, composée des entiers de $0$ à $n$. Il souhaite que vous deviniez cette permutation secrète. Pour cela, Little Cyan Fish vous autorise à effectuer au plus $1024$ requêtes de la forme suivante :

• ? i j : Obtenez l'indice $k$ ($0\le k\le n$) tel que $p_k=|p_i-p_j|$.

Bien entendu, pour qu'une requête soit valide, vous devez garantir que $i$ et $j$ sont deux entiers dans $[0,n]$. Par exemple, si $p_0=2,p_1=0,p_2=1$, la requête ? 0 2 renverra l'indice $2$, car $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish souhaite que vous élaboriez une stratégie pour trouver la permutation. Bien entendu, il ne veut pas que vous gagniez trop facilement. Il modifiera donc la permutation $p$ de manière adaptative pour vous piéger (voir « Interaction » pour plus de détails).

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un unique entier $T$ ($1\le T\le100$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne de l'entrée contient un unique entier $n$ ($1\le n\le1000$). L'interaction commence ensuite.

Interaction

Pour effectuer une requête, affichez une ligne au format suivant :

$$?\ i\ j$$

Ici, $i$ et $j$ sont deux entiers de $0$ à $n$. Vous devez garantir que le nombre de requêtes ne dépasse pas $1024$. En réponse, vous recevrez un entier $k$ tel que $p_k=|p_i-p_j|$.

Pour annoncer la réponse, affichez une ligne au format suivant :

$$!\ p_0\ p_1\ \ldots\ p_n$$

Ici, $p$ est la permutation que vous souhaitez annoncer.

Après avoir affiché une requête ou annoncé la réponse, n'oubliez pas d'afficher un saut de ligne et de vider le flux de sortie.

Dans ce problème, l'interacteur est adaptatif. Cela signifie que la permutation $p$ peut changer selon vos requêtes, tant qu'elle ne contredit pas les requêtes précédentes.

Exemples

Exemple d'interaction 1

Lecture:

1
3

Écriture:

? 2 2

Lecture:

1

Écriture:

? 0 3

Lecture:

3

Écriture:

! 2 0 3 1

Outil de test : Un outil est fourni pour aider les participants à développer et tester leurs solutions. Vous pouvez le télécharger depuis les pièces jointes. Son exécution avec l'option -h devrait expliquer son utilisation. L'outil ne met en œuvre que certains scénarios de test et une partie des fonctionnalités du véritable programme d'évaluation.