«Es un forajido y es famoso, Andrii Popa el valiente.

Día y noche cabalga, Cobra su tributo en el camino real Y en todas partes del país Los cazadores de ladrones huyen tan rápido como pueden»

— «Andrii Popa», Phoenix

Ghiță tiene una secuencia $S$ indexada desde $0$ de $N$ pesos enteros positivos. Como es el rey de los Cárpatos, quiere construir un árbol binario cuyos nodos tengan índices $0, 1, \ldots, N - 1$ tal que:

• El recorrido en inorden (inorder) del árbol produzca los nodos en orden creciente de índices. El recorrido en inorden de un árbol binario está formado por el recorrido en inorden del subárbol con raíz en el hijo izquierdo de la raíz (si dicho hijo existe), seguido del índice de la raíz, seguido del recorrido en inorden del subárbol con raíz en el hijo derecho de la raíz (si dicho hijo existe).
• Si el nodo $x$ es el padre del nodo $y$, entonces $S_x$ divide a $S_y$.

Recordamos que un árbol binario es una estructura de datos arbórea en la que cada nodo tiene como máximo dos hijos, denominados hijo izquierdo e hijo derecho.

Desafortunadamente, el famoso forajido Andrii Popa ha robado la secuencia $S$, y Ghiță ya no puede acceder a ella directamente. Usando tecnología avanzada (su teléfono móvil), puede, para cualesquiera dos subsecuencias continuas $[a, b]$ y $[c, d]$ de $S$, averiguar si $\gcd[a, b]$ es igual a $\gcd[c, d]$, donde $\gcd[x, y]$ es el máximo común divisor de $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Lamentablemente, la tecnología es bastante costosa: si Ghiță la utiliza más de $Q$ veces, tendrá que pagar una gran multa. Ayúdalo usando la tecnología como máximo $Q$ veces para construir el árbol deseado. Se garantiza que esto es posible. Se aceptará cualquier solución válida.

Interacción

El concursante debe incluir la cabecera popa.h (C / C++) o implementar popa.pas (Pascal). El concursante necesita implementar la siguiente función:

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

Esta función debe devolver la raíz del árbol y establecer $\text{Left}_i$ y $\text{Right}_i$ como los hijos izquierdo y derecho del nodo $i$, respectivamente. Si el nodo $i$ no tiene hijo izquierdo, entonces $\text{Left}_i$ debe ser $-1$. Si el nodo $i$ no tiene hijo derecho, entonces $\text{Right}_i$ debe ser $-1$. Left y Right apuntan a dos arreglos de tamaño exactamente $N$ que ya han sido reservados.

La función solve puede ser llamada como máximo $5$ veces en el transcurso de una sola ejecución. Sugerimos tener cuidado con las variables globales.

El concursante puede usar la siguiente función:

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

Esta función devolverá $1$ si y solo si $\gcd[a, b]$ es igual a $\gcd[c, d]$, donde $0 \le a \le b < N$ y $0 \le c \le d < N$, y $0$ en caso contrario.

Subtareas

Subtarea 1 (37 puntos)

• $N = 100$
• $Q = 10000$

Subtarea 2 (24 puntos)

• $N = 1000$
• $Q = 20000$

Subtarea 3 (39 puntos)

• $N = 1000$
• $Q = 2000$

Ejemplos

Un ejemplo de la interacción para $S = [12, 4, 16, 2, 2, 20]$ es:

Nota

Un ejemplo de un árbol del tipo que Ghiță quiere para el ejemplo anterior es: