Ceci est un problème interactif.

Les juges travaillent sur la stratégie du programme du jury pour la version modifiée du problème J du concours actuel.

Dans ce problème, 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. Alice peut modifier la permutation au cours du processus tant qu'elle reste cohérente avec ses réponses précédentes.

Les juges prévoient de créer un AliceBot qui effectuera les opérations suivantes. Il y a deux phases : la phase de questions et la phase de réponse.

Dans la phase de questions, le juge communique un entier $N$ à l'AliceBot. Ensuite, l'AliceBot doit répondre à certaines questions posées par le juge concernant la permutation.

Dans la phase de réponse suivante, l'AliceBot doit composer deux permutations différentes $a_1, \dots, a_N$ et $b_1, \dots, b_N$ qui sont cohérentes avec les réponses données lors de la phase précédente.

Le juge qui pose les questions dispose d'une patience initiale $P = 2N$. Chaque fois que le juge pose une question, sa patience diminue.

Il existe trois types de questions que le juge peut poser :

• Type 1, formaté comme « ? 1 i j k » : le juge choisit trois entiers différents $i, j, k$ ($1 \le i, j, k \le N$), l'AliceBot examine 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). Chaque question de ce type diminue la patience du juge de 2.
• Type 2, formaté comme « ? 2 i j » : le juge choisit deux entiers différents $i, j$ ($1 \le i, j \le N$), et l'AliceBot répond $i$ si $a_i < a_j$, ou $j$ sinon. Chaque question de ce type diminue la patience du juge de 2.
• Type 3, formaté comme « ? 3 i j » : le juge choisit deux entiers différents $i, j$ ($1 \le i, j \le N$), et l'AliceBot indique la valeur minimale parmi $a_i$ et $a_j$. Chaque question de ce type diminue la patience du juge de 1.

Vous pouvez supposer que la patience du juge ne descendra jamais en dessous de 2 après avoir posé une question. Lorsque le juge décide qu'il a posé suffisamment de questions, la commande « ! » est envoyée à l'AliceBot, ce qui le fait passer à la phase de réponse.

Dans la phase de réponse, l'AliceBot communique au juge deux permutations $a_1, \dots, a_N$ et $b_1, \dots, b_N$. Ces deux permutations doivent être cohérentes avec toutes les réponses données lors de la phase de questions, et le nombre de positions $i$ telles que $a_i \neq b_i$ doit être d'au moins $\lceil p/2 \rceil$, où $p$ est la patience du juge à la fin de la phase de questions.

Comme le juge est trop paresseux, on vous demande d'implémenter l'AliceBot. Il peut être démontré que le problème est soluble pour tout $N$ possible selon les contraintes.

Interaction

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

Ensuite, le jury pose 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). Vous devez alors imprimer une ligne avec un seul entier : la médiane des valeurs $a_i, a_j$ et $a_k$.

Une question de type 2 est une ligne formatée comme « ? 2 i j » ($1 \le i, j \le N$ ; $i \neq j$). Vous devez alors imprimer une ligne avec un seul entier : $i$ si $a_i < a_j$, ou $j$ si $a_i > a_j$.

Une question de type 3 est une ligne formatée comme « ? 3 i j » ($1 \le i, j \le N$ ; $i \neq j$). Vous devez alors imprimer une ligne avec un seul entier : la valeur minimale parmi $a_i$ et $a_j$.

Soient $q_1$ le nombre total de questions de type 1, $q_2$ le nombre de questions de type 2, et $q_3$ le nombre de questions de type 3. Vous pouvez supposer que la valeur $p = 2N - 2q_1 - 2q_2 - q_3$ n'est pas inférieure à 2.

Pour passer à la phase de réponse, le programme du jury émet une ligne composée du signe « ! ». Après cela, vous devez imprimer deux lignes, la première contenant $N$ entiers séparés par des espaces $a_1, \dots, a_N$, et la seconde ligne contenant $N$ entiers séparés par des espaces $b_1, \dots, b_N$. Chacune de ces deux séquences doit être une permutation de $1, \dots, N$, et elles doivent différer dans au moins $\lceil p/2 \rceil$ positions.

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

Exemples

Entrée 1

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

Sortie 1

4
4
1
3 5 4 1 2
5 4 3 2 1