Il y a $N$ cyclistes $1, \dots, N$. Chaque cycliste possède une compétence distincte allant de $1$ à $N$, et lorsque deux cyclistes s'affrontent, celui ayant la compétence la plus élevée gagne toujours.

Les cyclistes aiment participer à des compétitions. Dans une compétition, les cyclistes sont ordonnés dans une liste cyclique. La compétition se déroule ensuite par manches. À chaque manche, un cycliste affronte chacun de ses voisins. S'il perd contre les deux, il est éliminé.

Vous ne connaissez pas les compétences des cyclistes et vous souhaitez les déterminer. Vous pouvez organiser des compétitions entre tous les cyclistes, en choisissant à chaque fois leur ordre dans la liste cyclique, et vous serez informé de la manche au cours de laquelle chaque cycliste a été éliminé.

Déterminez les compétences en utilisant le nombre optimal de compétitions, ou en utilisant $N$ compétitions pour obtenir un score partiel.

Protocole d'interaction

Chaque test contient plusieurs cas de test. L'interaction commence par une ligne contenant l'entier unique $T$ ($1 \le T \le 10^4$), le nombre de cas de test.

Chaque cas de test commence par une ligne contenant l'entier unique $N$ ($3 \le N \le 300$), le nombre de cyclistes.

Vous pouvez ensuite organiser des compétitions. Pour organiser une compétition, affichez une ligne « ? $a_1$ $a_2$ $\dots$ $a_n$ » — $a_k$ indique que le cycliste $a_k$ est à la $k$-ième position de la liste des cyclistes. La liste $a_1, \dots, a_n$ doit être une permutation de $1, \dots, n$.

La réponse à votre requête sera une ligne « $r_1$ $r_2$ $\dots$ $r_n$ » — $r_k$ satisfait $0 \le r_k < n$. Lorsque $r_k > 0$, cela indique que le cycliste à la $k$-ième position a été éliminé lors de la manche $r_k$ de la compétition. Si $r_k = 0$, alors ledit cycliste a gagné la compétition.

Une fois que vous avez déterminé les compétences des cyclistes, affichez une ligne « ! $s_1$ $s_2$ $\dots$ $s_n$ » — $s_k$ doit être égal à la compétence du cycliste $k$.

Si vous effectuez une requête invalide ou si vous essayez d'organiser plus de $N$ compétitions, votre solution recevra un verdict de réponse incorrecte (Wrong Answer). De plus, si l'ensemble des compétences que vous affichez est différent de l'ensemble des compétences que l'interacteur a en tête, votre solution recevra un verdict de réponse incorrecte. Dans les deux cas, l'interaction se terminera immédiatement. Sinon, vous recevrez un score tel que décrit dans la section de notation.

Notez que l'interacteur peut être adaptatif : les compétences réelles des cyclistes peuvent changer au cours de l'interaction, mais l'ensemble actuel des compétences sera toujours cohérent avec toutes les compétitions précédentes.

Sous-tâches

Pour chaque cas de test, soit $q$ le nombre de compétitions que votre solution a organisées. De plus, pour chaque $N$, soit $c_N$ le nombre minimum de compétitions nécessaires pour garantir la détermination des compétences.

Vous recevrez 100 points si $q \le c_N$ pour tous les cas de test. Sinon, vous recevrez 10 points. Notez que selon les contraintes du problème, recevoir 10 points nécessite de satisfaire $q \le N$ pour tous les cas de test.

Notation

Exemples

Entrée 1

1
5

Sortie 1

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

Remarque

Dans l'exemple, les compétences des cyclistes sont respectivement 4, 2, 1, 5, 3.

Lors de la première compétition organisée, les cyclistes sont ordonnés dans la liste [1, 2, 3, 4, 5]. La compétition se déroule comme suit ; à chaque manche, la liste des cyclistes est affichée, les cyclistes éliminés étant remplacés par X.

• À la manche 1 :

  • Le cycliste en position 3 (cycliste 3 avec compétence 1) perd contre les cyclistes en positions 2 et 4 (cyclistes 2, 4 avec compétences 2, 5) et est éliminé.
  • Le cycliste en position 5 (cycliste 5 avec compétence 3) perd contre les cyclistes en positions 4 et 1 (cyclistes 4, 1 avec compétences 5, 4) et est éliminé.
  • Le cycliste en position 1 (cycliste 1 avec compétence 4) bat les cyclistes en positions 5, 2 (cyclistes 5, 2 avec compétences 3, 2) et n'est donc pas éliminé.
  • Le cycliste en position 2 (cycliste 2 avec compétence 2) bat le cycliste en position 3 (cycliste 3 avec compétence 1) et n'est donc pas éliminé.
  • Le cycliste en position 4 (cycliste 4 avec compétence 5) bat les cyclistes en positions 3, 5 (cyclistes 3, 5 avec compétences 1, 3) et n'est donc pas éliminé.

• À la manche 2, la liste des cyclistes est [1, 2, X, 4, X].

  • Le cycliste en position 2 perd contre les cyclistes en positions 1 et 4 et est éliminé.
  • Le cycliste en position 1 bat le cycliste en position 2 et n'est donc pas éliminé.
  • Le cycliste en position 4 bat les deux autres cyclistes et n'est donc pas éliminé.

• À la manche 3, la liste des cyclistes est [1, X, X, 4, X].

  • Le cycliste en position 1 perd contre les cyclistes en positions 4 et 4 (qui sont le même cycliste) et est éliminé.
  • Le cycliste en position 4 bat le cycliste en position 1 et n'est donc pas éliminé.

Par conséquent, Le cycliste en position 1 a été éliminé à la manche 3. Le cycliste en position 2 a été éliminé à la manche 2. Le cycliste en position 3 a été éliminé à la manche 1. Le cycliste en position 4 a gagné la compétition. * Le cycliste en position 5 a été éliminé à la manche 1.

ce qui donne la réponse à la requête [3, 2, 1, 0, 1].

Lors de la deuxième compétition organisée, les cyclistes sont ordonnés dans la liste [1, 3, 5, 2, 4]. La compétition se déroule comme suit.

• À la manche 1 :

  • Le cycliste en position 2 (cycliste 3 avec compétence 1) perd contre les cyclistes en positions 1 et 3 (cyclistes 1, 5 avec compétences 4, 3) et est éliminé.
  • Le cycliste en position 4 (cycliste 2 avec compétence 2) perd contre les cyclistes en positions 3 et 5 (cyclistes 5, 4 avec compétences 3, 5) et est éliminé.
  • Le cycliste en position 1 (cycliste 1 avec compétence 4) bat le cycliste en position 2 (cycliste 3 avec compétence 1) et n'est donc pas éliminé.
  • Le cycliste en position 3 (cycliste 5 avec compétence 3) bat les cyclistes en positions 2, 4 (cyclistes 3, 2 avec compétences 1, 2) et n'est donc pas éliminé.
  • Le cycliste en position 5 (cycliste 4 avec compétence 5) bat les cyclistes en positions 4, 1 (cyclistes 2, 1 avec compétences 2, 4) et n'est donc pas éliminé.

• À la manche 2, la liste des cyclistes est [1, X, 5, X, 4].

  • Le cycliste en position 3 perd contre les cyclistes en positions 1 et 5 et est éliminé.
  • Le cycliste en position 1 bat le cycliste en position 3 et n'est donc pas éliminé.
  • Le cycliste en position 5 bat les deux autres cyclistes et n'est donc pas éliminé.

• À la manche 3, la liste des cyclistes est [1, X, X, X, 4].

  • Le cycliste en position 1 perd contre les cyclistes en positions 5 et 5 (qui sont le même cycliste) et est éliminé.
  • Le cycliste en position 5 bat le cycliste en position 1 et n'est donc pas éliminé.

Par conséquent, Le cycliste en position 1 a été éliminé à la manche 3. Le cycliste en position 2 a été éliminé à la manche 1. Le cycliste en position 3 a été éliminé à la manche 2. Le cycliste en position 4 a été éliminé à la manche 1. * Le cycliste en position 5 a gagné la compétition.

ce qui donne la réponse à la requête [3, 1, 2, 1, 0].