¡Es época de Navidad! Mientras la mayoría de los lugares de trabajo participan en intercambios de regalos de "Amigo Invisible", tu lugar de trabajo está tramando un plan más siniestro: descubrir los secretos de Santa.

Santa tiene una lista de "buenos o malos" para cada ser humano en la Tierra. Debido a que su contenido es muy sensible, la lista está escrita en norpolaco, un lenguaje arcano con $N$ letras. Para mayor seguridad, Santa ha cifrado esta lista con un cifrado de sustitución: una permutación $H$ de los números $1, 2, \dots, N$ que mapea cada letra norpolaca $i$ a una letra distinta $H(i)$. En tal cifrado, no hay dos letras que se mapeen a la misma letra de destino —formalmente, si $i \neq j$, entonces $H(i) \neq H(j)$—, ya que de lo contrario Santa no podría descifrar su lista. (Santa puede elegir mapear algunas letras a sí mismas, $H(i) = i$, solo para ser más astuto).

Afortunadamente para ti, el servidor de Santa fue programado con poco cuidado y está expuesto a la Internet pública. Tú y tus compañeros de trabajo esperan hackear el servidor de Santa, descifrar su lista y confirmar que todos ustedes son traviesos. (Los hackers siempre son traviesos).

El servidor fue construido para que Santa pudiera revisar rápidamente su lista sobre la marcha. Después de que un usuario se conecta al servidor, este le solicita ingresar la lista de $N$ enteros $H(1), H(2), \dots, H(N)$ que codifican la permutación $H$, verifica que esta lista sea correcta y luego descifra la lista secreta de Santa. A través de meses de investigación, has encontrado una vulnerabilidad de temporización en el canal lateral. Supongamos que escribes una permutación $Q$. Si $H = Q$, entonces el servidor otorga acceso instantáneamente. De lo contrario, considera un grafo con $N$ vértices y añade una arista desde cada vértice $i$ al vértice $H(Q(i))$. Has descubierto que el complejo algoritmo de autenticación del servidor tardará exactamente tantos segundos en responderte con un mensaje de error de Acceso Denegado como el número de componentes conexas en el grafo resultante.

Por ejemplo, supongamos que $N = 4$ y la permutación de cifrado $H$ es la siguiente:

Si intentas iniciar sesión en el servidor con la entrada 4 3 2 1, dado que esta permutación no coincide con $H$ y dado que el grafo descrito anteriormente tiene dos componentes conexas (una que contiene un ciclo de aristas $1 \to 4 \to 2 \to 1$ y otra que contiene solo el bucle propio $3 \to 3$), el servidor responderá con un mensaje de error de Acceso Denegado después de una demora de 2 segundos.

Ten en cuenta que si intentas iniciar sesión en el servidor varias veces con diferentes entradas $Q$, este autenticará $Q$ cada vez contra el mismo $H$ almacenado. No cambia $H$ de ninguna manera en respuesta a tus entradas.

Santa notará si su servidor es bombardeado con solicitudes no autorizadas. Has estimado que solo puedes realizar 1 510 intentos de inicio de sesión antes de generar demasiada sospecha. ¿Puedes encontrar una estrategia eficiente para determinar la permutación de cifrado?

Interacción

Este es un problema interactivo. La interacción comienza leyendo un entero $N$ ($1 \le N \le 220$) desde la entrada estándar, el número de letras en norpolaco. El juez no es adaptativo: la permutación oculta $H$ se elige en este momento y no cambiará durante el resto de la interacción.

Para intentar iniciar sesión en el servidor, imprime una línea con $N$ enteros separados por espacios $Q(1), \dots, Q(N)$, donde $Q$ es una permutación de $\{1, 2, \dots, N\}$. Luego, lee un solo entero desde la entrada estándar, la cantidad de tiempo en segundos que le toma al servidor responder a tu entrada.

Si esta demora es 0, has encontrado con éxito la permutación de cifrado $H$ y tu programa debe terminar. Si no, esta demora es el número de componentes conexas en el grafo construido de acuerdo con el procedimiento descrito anteriormente.

Puedes intentar iniciar sesión como máximo 1 510 veces. Si te quedas sin intentos, tu programa debe salir limpiamente (aunque será juzgado como incorrecto por no lograr descifrar la lista de "buenos o malos" de Santa).

Nota

No olvides vaciar el flujo de salida después de cada línea que imprimas y salir limpiamente después de que la interacción haya terminado. Por favor, asegúrate también de seguir el protocolo de interacción anterior exactamente con respecto a qué información imprimir en qué línea de salida: por ejemplo, si el protocolo requiere que imprimas una lista de enteros separados por espacios en una sola línea, el juez no aceptará cada entero en su propia línea.

Si el juez recibe una entrada inválida o inesperada, imprimirá -1 y luego saldrá inmediatamente. Tu programa debe detectar esto y salir limpiamente para recibir un veredicto de Respuesta Incorrecta (Wrong Answer). Si tu programa se bloquea esperando más interacción del juez, o intenta interpretar el -1 como el número de componentes, podrías recibir un veredicto de rechazo diferente (como Tiempo Límite Excedido o Error de Ejecución) en lugar de Respuesta Incorrecta.

Se te ha proporcionado una herramienta de línea de comandos para pruebas locales. La herramienta tiene comentarios en la parte superior que explican su uso.

Ejemplos

Entrada 1

3

Salida 1

1 2 3

Entrada 2

1

Salida 2

2 1 3

Entrada 3

2

Salida 3

3 1 2

Entrada 4

0