Este es un problema interactivo.

El mar, nos volvemos a encontrar. ¡Espero que también seas feliz en las próximas vacaciones de verano! Hace mucho tiempo, Una y Kamome ya eran buenos amigos.

Les gustaba jugar juegos. La última vez, el juego inventado por Una fue resuelto fácilmente gracias a la excelente estrategia de Kamome. Esta vez, Una ha traído un nuevo juego.

Una está pensando en un árbol con $n$ nodos. Kamome puede hacer como máximo $n$ consultas: * Kamome puede decirle a Una una permutación $P_1, P_2, \dots, P_n$ (donde $0 \le P_i \le n-1$ y todos los $P_i$ son distintos). Entonces Una le dice a Kamome la longitud del diámetro ponderado del árbol cuando se asigna un peso $2^{P_i}$ al nodo $i$.

Pero a veces Kamome se da cuenta de que Una está causando problemas. Más específicamente, hay casos en los que, por más preguntas que se hagan, no se puede determinar el árbol con certeza. En tales casos, Kamome puede informar que no hay solución.

Interacción

Este es un problema interactivo. Después de cada salida, debes vaciar el búfer de salida. Para vaciar el búfer de salida, puedes usar:

• C/C++: fflush(stdout) o cout.flush()
• Java y Kotlin: System.out.flush()
• Python: sys.stdout.flush()

Primero, debes leer el número de casos de prueba $T$ ($1 < T < 10^4$). Para cada caso de prueba, debes leer el tamaño del árbol $n$ ($2 \le n \le 100$, $\sum n^2 < 10^6$).

Para hacer una consulta, debes imprimir una línea en el formato "? $P_1 P_2 \dots P_n$" (donde $0 \le P_i \le n-1$ y $P_i \ne P_j$ para $1 < i < j \le n$). Luego, lees una cadena de $n$ caracteres que representa el diámetro ponderado del árbol en su representación binaria. Si la consulta no es válida, o si haces más de $n$ consultas en un caso de prueba, el juez imprime -1. Si lees -1, debes terminar inmediatamente para evitar un comportamiento indefinido.

Si determinas que es imposible determinar el árbol de manera única, debes imprimir "! NO". De lo contrario, debes imprimir una línea en el formato "! YES $u_1 v_1 u_2 v_2 \dots u_{n-1} v_{n-1}$", indicando que el árbol contiene las aristas $(u_i, v_i)$. Las aristas se pueden imprimir en cualquier orden.

Luego, lees la palabra "OK" o "WA", que indica si tu respuesta es correcta o no. Si lees "WA", debes terminar inmediatamente para evitar un comportamiento indefinido. Si el árbol no es determinable y sin embargo imprimes YES, incluso si tu respuesta es correcta, Una piensa que estás haciendo trampa, por lo que tu respuesta se considera incorrecta.

El juez no es adaptativo, por lo que la respuesta no cambia después de una consulta.

Ejemplos

Entrada 1

2
4
1110
1110
OK
3
111
OK

Salida 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

Nota

Se proporciona una herramienta de prueba para que los participantes desarrollen y prueben sus soluciones. Esta herramienta se puede descargar en los archivos adjuntos. Ejecutar la herramienta con la opción "-h" explica su uso. La herramienta de prueba solo implementa algunas funciones del juez real y solo implementa algunos escenarios de prueba.