Este es un problema interactivo.

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 preguntas para identificar esta permutación. Él puede hacer preguntas de dos tipos:

• Tipo 1, con el formato "? 1 i j k": Bob elige tres enteros diferentes $i, j, k$ ($1 \le i, j, k \le N$), Alice 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).
• Tipo 2, con el formato "? 2 i j": Bob elige dos enteros diferentes $i, j$ ($1 \le i, j \le N$), y Alice responde $i$ si $a_i < a_j$, o $j$ en caso contrario.

El juego parece ser demasiado fácil para Bob, así que Alice inventó nuevas reglas. Primero, Bob solo puede hacer $2N$ preguntas de tipo 1 y solo 2 preguntas de tipo 2. Segundo, Alice puede cambiar la permutación libremente siempre que sea consistente con todas las respuestas que se dieron anteriormente.

Ayuda a Bob a ganar y escribe el programa que identifica la permutación.

Interacción

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

Luego puedes hacer 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í). El programa del jurado imprime entonces una línea con un solo entero: la mediana de los valores $a_i, a_j$ y $a_k$. Puedes hacer una pregunta de este tipo no más de $2N$ veces.

Una pregunta de tipo 2 es una línea con el formato "? 2 i j" ($1 \le i, j \le N$; $i \neq j$). El programa del jurado imprime entonces una línea con un solo entero: $i$ si $a_i < a_j$, o $j$ si $a_i > a_j$. Puedes hacer una pregunta de este tipo no más de dos veces.

Cuando la permutación esté determinada de forma única, imprime la respuesta en una línea con el formato "! $a_1$ $a_2$ ... $a_N$".

Ten en cuenta que la interacción es adaptativa: el programa del jurado puede cambiar la permutación en cualquier momento siempre que sea consistente con las respuestas anteriores. En particular, si intentas adivinar la respuesta cuando aún no está determinada de forma única, el programa del jurado puede elegir inmediatamente otra y decir que te equivocaste.

No olvides imprimir el carácter de nueva línea y limpiar el búfer de salida después de imprimir una pregunta o una respuesta; de lo contrario, podrías obtener el error "Idleness Limit Exceeded".

Ejemplos

Entrada 1

5
4
4
2

Salida 1

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