”Han är en fredlös och han är berömd, Andrii Popa den modige.

Dag och natt rider han, Han kräver sin tribut längs landsvägen Och överallt i landet Springer tjuvfångarna sin väg så fort de kan”

— ”Andrii Popa”, Phoenix

Ghiță har en $0$-indexerad följd $S$ med $N$ positiva heltalsvikter. Eftersom han är kung av Karpaterna vill han konstruera ett binärt träd vars noder har index $0, 1, \ldots, N - 1$ sådant att:

• Inorder-traverseringen av trädet ger noderna i stigande indexordning. Inorder-traverseringen av ett binärt träd utgörs av inorder-traverseringen av delträdet med rot i rotens vänstra barn (om barnet finns), följt av rotens index, följt av inorder-traverseringen av delträdet med rot i rotens högra barn (om barnet finns).
• Om nod $x$ är förälder till nod $y$ så delar $S_x$ talet $S_y$.

Vi påminner om att ett binärt träd är en träddatastruktur där varje nod har högst två barn, vilka kallas vänster barn och höger barn.

Tyvärr har den berömde fredlöse Andrii Popa stulit följden $S$, och Ghiță kan inte längre komma åt den direkt. Med hjälp av avancerad teknik (sin mobiltelefon) kan han för varje par av sammanhängande delföljder $[a, b]$ och $[c, d]$ av $S$ ta reda på om $\gcd[a, b]$ är lika med $\gcd[c, d]$, där $\gcd[x, y]$ är den största gemensamma delaren för $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Tyvärr är tekniken ganska dyr — om Ghiță använder den fler än $Q$ gånger måste han betala dryga böter. Hjälp honom genom att använda tekniken högst $Q$ gånger för att bygga det önskade trädet. Det garanteras att detta är möjligt. Varje giltig lösning kommer att accepteras.

Interaktion

Tävlanden ska inkludera headern popa.h (C / C++) eller implementera popa.pas (Pascal). Tävlanden ska implementera följande funktion:

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

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

Denna funktion ska returnera trädets rot och sätta $\text{Left}_i$ respektive $\text{Right}_i$ till det vänstra och det högra barnet till nod $i$. Om nod $i$ saknar vänster barn ska $\text{Left}_i$ vara $-1$. Om nod $i$ saknar höger barn ska $\text{Right}_i$ vara $-1$. Left och Right pekar på två redan allokerade fält med storlek exakt $N$.

Funktionen solve kan anropas högst $5$ gånger under en och samma körning. Vi rekommenderar försiktighet med globala variabler.

Tävlanden får använda följande funktion:

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

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

Denna funktion returnerar $1$ om och endast om $\gcd[a, b]$ är lika med $\gcd[c, d]$, där $0 \le a \le b < N$ och $0 \le c \le d < N$, och $0$ annars.

Deluppgifter

Deluppgift 1 (37 poäng)

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

Deluppgift 2 (24 poäng)

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

Deluppgift 3 (39 poäng)

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

Exempel

Ett exempel på interaktionen för $S = [12, 4, 16, 2, 2, 20]$ är:

Kommentar

Ett exempel på ett träd av det slag som Ghiță vill ha för föregående exempel är: