Este es un problema interactivo.

Los jueces están trabajando en la estrategia para el programa del jurado para la versión modificada del problema J del concurso actual.

En ese problema, Alice inventa secretamente una permutación de los primeros $N$ enteros $a_1, a_2, \dots, a_N$ y le dice $N$ a Bob. Bob hace algunas preguntas para identificar esta permutación. Alice puede cambiar la permutación en el proceso siempre y cuando sea consistente con sus respuestas anteriores.

Los jueces planean crear un AliceBot que haga lo siguiente. Hay dos fases: la fase de preguntas y la fase de respuesta.

En la fase de preguntas, el juez le dice a AliceBot un entero $N$. Luego, AliceBot debe responder algunas preguntas que el juez hace sobre la permutación.

En la fase de respuesta posterior, AliceBot debe componer dos permutaciones diferentes $a_1, \dots, a_N$ y $b_1, \dots, b_N$ que sean consistentes con las respuestas de la fase anterior.

El juez que hace las preguntas tiene una paciencia inicial $P = 2N$. Cada vez que el juez hace una pregunta, su paciencia disminuye.

Hay tres tipos de preguntas que el juez puede hacer:

• Tipo 1, con formato “? 1 i j k”: el juez elige tres enteros diferentes $i, j, k$ ($1 \le i, j, k \le N$), AliceBot observa los tres enteros $a_i, a_j$ y $a_k$, y le dice a Bob el valor de su mediana (el que no es ni el mínimo ni el máximo). Cada pregunta de este tipo disminuye la paciencia del juez en 2.
• Tipo 2, con formato “? 2 i j”: el juez elige dos enteros diferentes $i, j$ ($1 \le i, j \le N$), y AliceBot responde $i$ si $a_i < a_j$, o $j$ en caso contrario. Cada pregunta de este tipo disminuye la paciencia del juez en 2.
• Tipo 3, con formato “? 3 i j”: el juez elige dos enteros diferentes $i, j$ ($1 \le i, j \le N$), y AliceBot dice el valor mínimo entre $a_i$ y $a_j$. Cada pregunta de este tipo disminuye la paciencia del juez en 1.

Puedes asumir que la paciencia del juez nunca bajará de 2 después de hacer una pregunta. Cuando el juez decide que ha hecho suficientes preguntas, se envía el comando “!” al AliceBot, cambiando a la fase de respuesta.

En la fase de respuesta, AliceBot le dice al juez dos permutaciones $a_1, \dots, a_N$ y $b_1, \dots, b_N$. Estas dos permutaciones deben ser consistentes con todas las respuestas dadas en la fase de preguntas, y el número de posiciones $i$ tales que $a_i \neq b_i$ debe ser al menos $\lceil p/2 \rceil$, donde $p$ es la paciencia del juez al final de la fase de preguntas.

Debido a que el juez es demasiado perezoso, se te pide implementar el AliceBot. Se puede demostrar que el problema es resoluble para cada $N$ posible dentro de las restricciones.

Interacción

Primero, el programa del jurado te dice un entero $N$ en una línea separada ($4 \le N \le 50\,000$).

Luego, el jurado hace preguntas.

Una pregunta de tipo 1 es una línea con el formato “? 1 i j k” ($1 \le i, j, k \le N$; $i, j$ y $k$ son distintos entre sí). Luego imprimes una línea con un solo entero: la mediana de los valores $a_i, a_j$ y $a_k$.

Una pregunta de tipo 2 es una línea con el formato “? 2 i j” ($1 \le i, j \le N$; $i \neq j$). Luego imprimes una línea con un solo entero: $i$ si $a_i < a_j$, o $j$ si $a_i > a_j$.

Una pregunta de tipo 3 es una línea con el formato “? 3 i j” ($1 \le i, j \le N$; $i \neq j$). Luego imprimes una línea con un solo entero: el valor mínimo entre $a_i$ y $a_j$.

Sea $q_1$ el total de preguntas de tipo 1, $q_2$ el total de preguntas de tipo 2 y $q_3$ el total de preguntas de tipo 3. Puedes asumir que el valor $p = 2N - 2q_1 - 2q_2 - q_3$ no es menor que 2.

Para cambiar a la fase de respuesta, el programa del jurado emite una línea que consiste en el signo ‘!’. Después de eso, debes imprimir dos líneas: la primera línea contiene $N$ enteros separados por espacios $a_1, \dots, a_N$, y la segunda línea contiene $N$ enteros separados por espacios $b_1, \dots, b_N$. Cada una de estas dos secuencias debe ser una permutación de $1, \dots, N$, y deben diferir en al menos $\lceil p/2 \rceil$ posiciones.

No olvides imprimir el carácter de nueva línea y vaciar el búfer de salida después de imprimir las respuestas y después de imprimir cada permutación; de lo contrario, podrías obtener el error “Idleness Limit Exceeded”.

Ejemplos

Entrada 1

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

Salida 1

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