«È un fuorilegge ed è famoso, Andrii Popa il coraggioso.

Giorno e notte cavalca, Riscuote il suo tributo sulla strada maestra E ovunque nel paese I cacciatori di ladri scappano più veloce che possono»

— «Andrii Popa», Phoenix

Ghiță possiede una sequenza $S$ indicizzata da $0$ di $N$ pesi interi positivi. Poiché è il re dei Carpazi, vuole costruire un albero binario i cui nodi abbiano indici $0, 1, \ldots, N - 1$ tale che:

• La visita simmetrica (inorder) dell'albero produca i nodi in ordine crescente di indice. La visita simmetrica di un albero binario è formata dalla visita simmetrica del sottoalbero radicato nel figlio sinistro della radice (se tale figlio esiste), seguita dall'indice della radice, seguita dalla visita simmetrica del sottoalbero radicato nel figlio destro della radice (se tale figlio esiste).
• Se il nodo $x$ è il padre del nodo $y$, allora $S_x$ divide $S_y$.

Ricordiamo che un albero binario è una struttura dati ad albero in cui ogni nodo ha al massimo due figli, detti figlio sinistro e figlio destro.

Sfortunatamente, il famoso fuorilegge Andrii Popa ha rubato la sequenza $S$, e Ghiță non può più accedervi direttamente. Utilizzando una tecnologia avanzata (il suo telefono cellulare), egli può, per qualsiasi coppia di sottosequenze contigue $[a, b]$ e $[c, d]$ di $S$, scoprire se $\gcd[a, b]$ è uguale a $\gcd[c, d]$, dove $\gcd[x, y]$ è il massimo comun divisore di $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Purtroppo la tecnologia è piuttosto costosa: se Ghiță la usa più di $Q$ volte, dovrà pagare una multa salata. Aiutalo usando la tecnologia al massimo $Q$ volte per costruire l'albero desiderato. È garantito che ciò sia possibile. Qualsiasi soluzione valida verrà accettata.

Interazione

Il concorrente deve includere l'header popa.h (C / C++) oppure implementare popa.pas (Pascal). Il concorrente deve implementare la seguente funzione:

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

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

Questa funzione deve restituire la radice dell'albero e impostare $\text{Left}_i$ e $\text{Right}_i$ rispettivamente al figlio sinistro e al figlio destro del nodo $i$. Se il nodo $i$ non ha un figlio sinistro, allora $\text{Left}_i$ deve essere $-1$. Se il nodo $i$ non ha un figlio destro, allora $\text{Right}_i$ deve essere $-1$. Left e Right puntano a due array di dimensione esattamente $N$ che sono già stati allocati.

La funzione solve può essere chiamata al massimo $5$ volte nel corso di una singola esecuzione. Suggeriamo di fare attenzione alle variabili globali.

Il concorrente può utilizzare la seguente funzione:

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

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

Questa funzione restituirà $1$ se e solo se $\gcd[a, b]$ è uguale a $\gcd[c, d]$, dove $0 \le a \le b < N$ e $0 \le c \le d < N$, e $0$ altrimenti.

Subtask

Subtask 1 (37 punti)

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

Subtask 2 (24 punti)

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

Subtask 3 (39 punti)

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

Esempi

Un esempio di interazione per $S = [12, 4, 16, 2, 2, 20]$ è:

Note

Un esempio di albero del tipo voluto da Ghiță per l'esempio precedente è: