Ceci est un problème interactif.

Alice invente secrètement une permutation des $N$ premiers entiers $a_1, a_2, \dots, a_N$ et communique $N$ à Bob.

Bob pose des questions pour identifier cette permutation. Il peut poser des questions de deux types :

• Type 1, formaté comme « ? 1 i j k » : Bob choisit trois entiers distincts $i, j, k$ ($1 \le i, j, k \le N$), Alice regarde les trois entiers $a_i, a_j$ et $a_k$, et indique à Bob la valeur de leur médiane (celle qui n'est ni le minimum ni le maximum).
• Type 2, formaté comme « ? 2 i j » : Bob choisit deux entiers différents $i, j$ ($1 \le i, j \le N$), et Alice répond $i$ si $a_i < a_j$, ou $j$ sinon.

Le jeu semble trop facile pour Bob, alors Alice a inventé de nouvelles règles. Premièrement, Bob ne peut poser que $2N$ questions de type 1 et seulement 2 questions de type 2. Deuxièmement, Alice peut modifier la permutation librement tant qu'elle reste cohérente avec toutes les réponses données précédemment.

Aidez Bob à gagner et écrivez le programme qui identifie la permutation.

Interaction

Le programme du jury vous donne d'abord un entier $N$ sur une ligne séparée ($4 \le N \le 60\,000$).

Ensuite, vous pouvez poser des questions.

Une question de type 1 est une ligne formatée comme « ? 1 i j k » ($1 \le i, j, k \le N$ ; $i, j$ et $k$ sont distincts deux à deux). Le programme du jury imprime alors une ligne avec un seul entier : la médiane des valeurs $a_i, a_j$ et $a_k$. Vous ne pouvez pas poser plus de $2N$ questions de ce type.

Une question de type 2 est une ligne formatée comme « ? 2 i j » ($1 \le i, j \le N$ ; $i \neq j$). Le programme du jury imprime alors une ligne avec un seul entier : $i$ si $a_i < a_j$, ou $j$ si $a_i > a_j$. Vous ne pouvez pas poser plus de deux questions de ce type.

Lorsque la permutation est déterminée de manière unique, imprimez la réponse sur une ligne formatée comme « ! a_1 a_2 ... a_N ».

Notez que l'interaction est adaptative : le programme du jury peut changer la permutation à tout moment tant qu'elle est cohérente avec les réponses passées. En particulier, si vous essayez de deviner la réponse alors qu'elle n'est pas encore déterminée de manière unique, le programme du jury peut immédiatement en choisir une autre et dire que vous avez tort.

N'oubliez pas d'imprimer le caractère de saut de ligne et de vider le tampon de sortie après avoir imprimé une question ou une réponse, sinon vous pourriez obtenir l'erreur « Idleness Limit Exceeded ».

Exemples

Entrée 1

5
4
4
2

Sortie 1

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