«Han er fredløs og han er berømt, Andrii Popa den modige.

Dag og natt rir han, Han krever sin skatt langs hovedveien Og overalt i landet Løper tyvefangerne sin vei så fort de kan»

— «Andrii Popa», Phoenix

Ghiță har en $0$-indeksert følge $S$ med $N$ positive heltallsvekter. Siden han er kongen av Karpatene, ønsker han å konstruere et binært tre hvis noder har indekser $0, 1, \ldots, N - 1$ slik at:

• Inorder-traverseringen av treet gir nodene i stigende rekkefølge etter indeks. Inorder-traverseringen av et binært tre består av inorder-traverseringen av undertreet med rot i rotens venstre barn (hvis barnet finnes), etterfulgt av rotens indeks, etterfulgt av inorder-traverseringen av undertreet med rot i rotens høyre barn (hvis barnet finnes).
• Hvis node $x$ er forelder til node $y$, så deler $S_x$ tallet $S_y$.

Vi minner om at et binært tre er en tredatastruktur der hver node har høyst to barn, kalt venstre barn og høyre barn.

Dessverre har den berømte fredløse Andrii Popa stjålet følgen $S$, og Ghiță har ikke lenger direkte tilgang til den. Ved hjelp av avansert teknologi (mobiltelefonen sin) kan han for ethvert par av sammenhengende delfølger $[a, b]$ og $[c, d]$ av $S$ finne ut om $\gcd[a, b]$ er lik $\gcd[c, d]$, der $\gcd[x, y]$ er største felles divisor for $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Dessverre er denne teknologien ganske dyr — hvis Ghiță bruker den mer enn $Q$ ganger, må han betale en stor bot. Hjelp ham ved å bruke teknologien høyst $Q$ ganger for å bygge det ønskede treet. Det er garantert at dette er mulig. Enhver gyldig løsning vil bli godkjent.

Interaksjon

Deltakeren skal inkludere headerfilen popa.h (C / C++) eller implementere popa.pas (Pascal). Deltakeren må implementere følgende funksjon:

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

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

Denne funksjonen skal returnere roten i treet, og sette $\text{Left}_i$ og $\text{Right}_i$ til henholdsvis venstre og høyre barn av node $i$. Hvis node $i$ ikke har noe venstre barn, skal $\text{Left}_i$ være $-1$. Hvis node $i$ ikke har noe høyre barn, skal $\text{Right}_i$ være $-1$. Left og Right peker på to tabeller med størrelse nøyaktig $N$ som allerede er allokert.

Funksjonen solve kan bli kalt høyst $5$ ganger i løpet av én enkelt kjøring. Vi anbefaler å være forsiktig med globale variabler.

Deltakeren kan bruke følgende funksjon:

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

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

Denne funksjonen returnerer $1$ hvis og bare hvis $\gcd[a, b]$ er lik $\gcd[c, d]$, der $0 \le a \le b < N$ og $0 \le c \le d < N$, og $0$ ellers.

Deloppgaver

Deloppgave 1 (37 poeng)

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

Deloppgave 2 (24 poeng)

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

Deloppgave 3 (39 poeng)

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

Eksempler

Et eksempel på interaksjonen for $S = [12, 4, 16, 2, 2, 20]$ er:

Merknad

Et eksempel på et tre av den typen Ghiță ønsker for det foregående eksempelet er: