Ceci est un problème interactif.

La mer, nous nous retrouvons. Je vous souhaite d'être également heureux pendant les prochaines vacances d'été ! Il y a bien longtemps, Una et Kamome étaient déjà de bons amis.

Elles aimaient jouer à des jeux. La dernière fois, le jeu inventé par Una a été facilement résolu grâce à l'excellente stratégie de Kamome. Cette fois, Una a apporté un nouveau jeu.

Una pense à un arbre à $n$ sommets. Kamome peut poser au maximum $n$ questions :

• Kamome peut donner à Una une permutation $P_1, P_2, \dots, P_n$ (où $0 \le P_i \le n-1$ et tous les $P_i$ sont distincts). Una indique alors à Kamome la longueur du diamètre pondéré de l'arbre lorsqu'un poids $2^{P_i}$ est attribué au sommet $i$.

Mais parfois, Kamome se rend compte qu'Una pose des problèmes. Plus précisément, il existe des cas où, peu importe le nombre de questions posées, il est impossible de déterminer l'arbre avec certitude. Dans de tels cas, Kamome peut indiquer qu'il n'y a pas de solution.

Interaction

Ceci est un problème interactif. Après chaque sortie, vous devez vider le tampon de sortie. Pour vider le tampon de sortie, vous pouvez utiliser :

• C/C++ : fflush(stdout) ou cout.flush()
• Java et Kotlin : System.out.flush()
• Python : sys.stdout.flush()

Tout d'abord, vous devez lire le nombre de jeux d'essais $T$ ($1 < T < 10^4$). Pour chaque jeu d'essais, vous devez lire la taille de l'arbre $n$ ($2 \le n \le 100$, $\sum n^2 < 10^6$).

Pour faire une demande, vous devez afficher une ligne au format "? $P_1 P_2 \dots P_n$" (où $0 \le P_i \le n-1$ et $P_i \ne P_j$ pour $1 < i < j \le n$). Ensuite, vous lirez une chaîne de $n$ caractères représentant le diamètre pondéré de l'arbre dans sa représentation binaire. Si la demande est invalide, ou si vous faites plus de $n$ demandes dans un jeu d'essais, le juge affichera -1. Si vous lisez -1, vous devez immédiatement terminer votre programme pour éviter un comportement indéterminé.

Si vous déterminez qu'il est impossible de déterminer l'arbre de manière unique, vous devez afficher "! NO". Sinon, vous devez afficher une ligne au format "! YES $u_1 v_1 u_2 v_2 \dots u_{n-1} v_{n-1}$", indiquant que l'arbre contient les arêtes $(u_i, v_i)$. Les arêtes peuvent être affichées dans n'importe quel ordre.

Ensuite, vous lirez le mot "OK" ou "WA", indiquant si votre réponse est correcte ou non. Si vous lisez "WA", vous devez immédiatement terminer votre programme pour éviter un comportement indéterminé. Si l'arbre n'est pas déterminable et que vous affichez tout de même YES, même si votre réponse est correcte, Una considérera que vous trichez et votre réponse sera comptée comme fausse.

Le juge n'est pas adaptatif, la réponse ne change donc pas après une demande.

Exemples

Entrée 1

2
4
1110
1110
OK
3
111
OK

Sortie 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

Remarque

Un outil de test est fourni pour aider les participants à développer et tester leurs solutions. Vous pouvez télécharger cet outil dans les fichiers joints. Exécuter l'outil avec l'option "-h" explique son utilisation. L'outil de test n'implémente que certaines fonctionnalités du juge réel et seulement certains scénarios de test.