„Hann er útlagi og hann er frægur, Andrii Popa hinn hugrakki.

Dag og nótt ríður hann, Hann tekur skatt sinn á þjóðveginum Og alls staðar í landinu Hlaupa þjófafangararnir í burtu eins hratt og þeir geta“

— „Andrii Popa“, Phoenix

Ghiță á $0$-vísaða runu $S$ af $N$ jákvæðum heiltöluþyngdum. Þar sem hann er konungur Karpatafjalla vill hann smíða tvíundartré þar sem hnútarnir hafa vísana $0, 1, \ldots, N - 1$ þannig að:

• Innröðunarferð (inorder traversal) um tréð skilar hnútunum í hækkandi röð eftir vísum. Innröðunarferð um tvíundartré myndast af innröðunarferð um hluttréð með rót í vinstra barni rótarinnar (ef barnið er til), þar á eftir kemur vísir rótarinnar, og loks innröðunarferð um hluttréð með rót í hægra barni rótarinnar (ef barnið er til).
• Ef hnútur $x$ er foreldri hnúts $y$ þá gengur $S_x$ upp í $S_y$.

Við rifjum upp að tvíundartré er trjágagnagrind þar sem hver hnútur á í mesta lagi tvö börn, sem kallast vinstra barn og hægra barn.

Því miður hefur hinn frægi útlagi Andrii Popa stolið rununni $S$, og Ghiță getur ekki lengur nálgast hana beint. Með háþróaðri tækni (farsímanum sínum) getur hann, fyrir hvaða tvær samfelldar hlutrunur $[a, b]$ og $[c, d]$ sem er úr $S$, komist að því hvort $\gcd[a, b]$ sé jafnt $\gcd[c, d]$, þar sem $\gcd[x, y]$ er stærsti samdeilir talnanna $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Því miður er tæknin nokkuð dýr — ef Ghiță notar hana oftar en $Q$ sinnum þarf hann að greiða háa sekt. Hjálpaðu honum með því að nota tæknina í mesta lagi $Q$ sinnum til að smíða tréð sem óskað er eftir. Það er tryggt að þetta sé hægt. Sérhver gild lausn verður samþykkt.

Samskipti

Keppandinn skal fella inn hausaskrána popa.h (C / C++) eða útfæra popa.pas (Pascal). Keppandinn þarf að útfæra eftirfarandi fall:

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

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

Þetta fall á að skila rót trésins og setja $\text{Left}_i$ og $\text{Right}_i$ sem vinstra og hægra barn hnúts $i$, í þessari röð. Ef hnútur $i$ á ekki vinstra barn skal $\text{Left}_i$ vera $-1$. Ef hnútur $i$ á ekki hægra barn skal $\text{Right}_i$ vera $-1$. Left og Right benda á tvö fylki af stærð nákvæmlega $N$ sem þegar hefur verið úthlutað.

Fallið solve getur verið kallað í mesta lagi $5$ sinnum í einni keyrslu. Við mælum með að fara varlega með víðværar breytur.

Keppandinn má nota eftirfarandi fall:

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

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

Þetta fall skilar $1$ ef og aðeins ef $\gcd[a, b]$ er jafnt $\gcd[c, d]$, þar sem $0 \le a \le b < N$ og $0 \le c \le d < N$, en $0$ annars.

Undirverkefni

Undirverkefni 1 (37 stig)

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

Undirverkefni 2 (24 stig)

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

Undirverkefni 3 (39 stig)

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

Dæmi

Dæmi um samskiptin fyrir $S = [12, 4, 16, 2, 2, 20]$ er:

Athugasemd

Dæmi um tré af þeirri gerð sem Ghiță vill fyrir fyrra dæmið er: