Aidos ha ideado un rompecabezas y ha desafiado a Temirulan a resolverlo. Él eligió una secuencia $a$ de $n$ enteros no negativos distintos numerados del 1 al $n$: $a_1, a_2, \dots, a_n$.

Temirulan puede realizar dos tipos de preguntas:

• ask — Revela el número en la posición $i$ de la secuencia dada.
• get_pairwise_xor — Para la secuencia dada de números enteros distintos: $i_1, i_2, \dots, i_k$, obtiene un conjunto de valores de $xor$ por pares para los elementos de la secuencia $a$ en los índices $i_1, i_2, \dots, i_k$, $\{a_{i_x} \oplus a_{i_y} \mid 1 \leq x, y \leq k\}$.

Por ejemplo, supongamos que Aidos ha elegido la secuencia $[1, 5, 6, 3]$. Entonces, para la pregunta ask(2), Aidos responderá con el número 5 y para la pregunta get_pairwise_xor({3, 4}), Aidos responderá con la secuencia $[0, 0, 5, 5]$, porque:

• $a_3 \oplus a_4 = 6 \oplus 3 = 5$
• $a_4 \oplus a_3 = 3 \oplus 6 = 5$
• $a_3 \oplus a_3 = 6 \oplus 6 = 0$
• $a_4 \oplus a_4 = 3 \oplus 3 = 0$.

Temirulan no pudo resolver el rompecabezas y tu tarea es ayudarlo. Encuentra la secuencia oculta utilizando las preguntas descritas anteriormente.

Entrada

TUS ENVÍOS NO DEBEN LEER DE LA ENTRADA ESTÁNDAR, IMPRIMIR A LA SALIDA ESTÁNDAR NI INTERACTUAR CON NINGÚN OTRO ARCHIVO.

Tu tarea es implementar la siguiente función: int[] guess(int n)

• $n$: la longitud de la secuencia oculta.
• La función se llama exactamente una vez para cada prueba.
• La función debe devolver la secuencia oculta en el mismo orden.

Tu función puede llamar a las siguientes funciones:

1. int ask(int i)

   • $i$: índice del número en la secuencia, $1 \leq i \leq n$.
   • La función devuelve el $i$-ésimo número de la secuencia oculta.

2. int[] get_pairwise_xor(int[] pos)

   • $pos$: lista no vacía de índices de la secuencia.
   • Todos los elementos en $pos$ deben ser enteros distintos.
   • Sea $k$ el número de elementos en $pos$. Entonces $1 \leq pos_i \leq n$ para cada $1 \leq i \leq k$.
   • La función devuelve una lista ordenada de $k^2$ elementos: un conjunto de valores $xor$ por pares, $\{a_{pos_x} \oplus a_{pos_y} \mid 1 \leq x, y \leq k\}$.

Puedes llamar a ambas funciones no más de 200 veces en total para cada prueba. Si se viola alguna de las condiciones anteriores, tu programa recibirá un veredicto de Wrong Answer. De lo contrario, tu programa recibirá un veredicto de Accepted y tu puntuación se calculará en función del número total de llamadas a las funciones ask y get_pairwise_xor (consulta la sección "Subtareas").

Subtareas

• $2 \leq n \leq 100$
• $0 \leq a_i \leq 10^9$ para cada $1 \leq i \leq n$.

En esta tarea, el evaluador NO es adaptativo. Esto significa que la secuencia $a$ está fijada al comienzo de la ejecución del evaluador y no depende de las llamadas de tu programa.

1. (6 puntos) $n \leq 4$
2. (94 puntos) Sin restricciones adicionales. Para esta subtarea, tu puntuación se calcula de la siguiente manera. Sea $q$ el número total de llamadas a las funciones ask y get_pairwise_xor.
   • Si $q \leq 15$, tu puntuación es 94.
   • Si $15 < q \leq 40$, tu puntuación es $84 - 2(q - 16)$.
   • Si $40 < q \leq 50$, tu puntuación es 35.
   • De lo contrario, tu puntuación es 0.

Ten en cuenta que tu puntuación para cada subtarea es la puntuación mínima entre todos los resultados en las pruebas de la subtarea correspondiente.

Nota

La operación $xor$ es el OR exclusivo a nivel de bits.

Sea la secuencia oculta $a = [1, 5, 6, 3]$. El evaluador llama a la función.

Ejemplos

Entrada 1

ask(2)
get_pairwise_xor({1, 2, 3})
ask(3)
get_pairwise_xor({4, 2})
get_pairwise_xor({2})

Salida 1

5
{0, 0, 0, 3, 3, 4, 4, 7, 7}
6
{0, 0, 6, 6}
{0}

El evaluador de muestra lee la entrada en el siguiente formato:

• Línea 1: $n$
• Línea 2: $a_1, a_2, \dots, a_n$

PUEDES DESCARGAR xoractive.zip en el sistema, el cual contiene ejemplos para los lenguajes Java, C++11, FPC y Python 2.

Todos los ejemplos de llamadas a las funciones se pueden encontrar arriba. Para Python 2, debes implementar la función def guess(n, interactor), donde interactor es una instancia de la clase que se está probando. Las funciones ask y get_pairwise_xor son métodos de esta clase.

xoractive.zip contiene ejemplos de soluciones para cada lenguaje.

Para las soluciones en lenguaje Java, el archivo y la clase deben llamarse Xoractive.java y Xoractive respectivamente.

Para las soluciones en lenguaje Pascal, el archivo debe llamarse xoractive.pas.