”Hän on lainsuojaton ja hän on kuuluisa, Andrii Popa rohkea.

Päivin ja öin hän ratsastaa, Hän kerää veronsa valtatiellä Ja kaikkialla maassa Varkaidenpyytäjät juoksevat pakoon minkä jaloistaan pääsevät”

— ”Andrii Popa”, Phoenix

Ghițălla on $0$-indeksoitu jono $S$, jossa on $N$ positiivista kokonaislukupainoa. Koska hän on Karpaattien kuningas, hän haluaa muodostaa binääripuun, jonka solmujen indeksit ovat $0, 1, \ldots, N - 1$ siten, että:

• Puun sisäjärjestysläpikäynti (inorder traversal) tuottaa solmut indeksien mukaisessa kasvavassa järjestyksessä. Binääripuun sisäjärjestysläpikäynti muodostuu juuren vasemman lapsen virittämän alipuun sisäjärjestysläpikäynnistä (jos kyseinen lapsi on olemassa), jota seuraa juuren indeksi ja sen jälkeen juuren oikean lapsen virittämän alipuun sisäjärjestysläpikäynti (jos kyseinen lapsi on olemassa).
• Jos solmu $x$ on solmun $y$ vanhempi, niin $S_x$ jakaa luvun $S_y$.

Muistutamme, että binääripuu on puutietorakenne, jossa jokaisella solmulla on enintään kaksi lasta, joita kutsutaan vasemmaksi lapseksi ja oikeaksi lapseksi.

Valitettavasti kuuluisa lainsuojaton Andrii Popa on varastanut jonon $S$, eikä Ghiță voi enää tarkastella sitä suoraan. Kehittyneen teknologian (matkapuhelimensa) avulla hän voi mille tahansa kahdelle jonon $S$ yhtenäiselle osajonolle $[a, b]$ ja $[c, d]$ selvittää, onko $\gcd[a, b]$ yhtä suuri kuin $\gcd[c, d]$, missä $\gcd[x, y]$ on lukujen $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$ suurin yhteinen tekijä. Valitettavasti tämä teknologia on melko kallista — jos Ghiță käyttää sitä yli $Q$ kertaa, hän joutuu maksamaan suuret sakot. Auta häntä muodostamaan haluttu puu käyttämällä teknologiaa enintään $Q$ kertaa. On taattu, että tämä on mahdollista. Mikä tahansa kelvollinen ratkaisu hyväksytään.

Vuorovaikutus

Kilpailijan tulee sisällyttää otsikkotiedosto popa.h (C / C++) tai toteuttaa popa.pas (Pascal). Kilpailijan tulee toteuttaa seuraava funktio:

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

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

Tämän funktion tulee palauttaa puun juuri sekä asettaa $\text{Left}_i$ ja $\text{Right}_i$ solmun $i$ vasemmaksi ja oikeaksi lapseksi vastaavasti. Jos solmulla $i$ ei ole vasenta lasta, arvon $\text{Left}_i$ tulee olla $-1$. Jos solmulla $i$ ei ole oikeaa lasta, arvon $\text{Right}_i$ tulee olla $-1$. Left ja Right osoittavat kahteen valmiiksi varattuun taulukkoon, joiden koko on täsmälleen $N$.

Funktiota solve voidaan kutsua enintään $5$ kertaa yhden ajon aikana. Suosittelemme varovaisuutta globaalien muuttujien kanssa.

Kilpailija voi käyttää seuraavaa funktiota:

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

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

Tämä funktio palauttaa $1$, jos ja vain jos $\gcd[a, b]$ on yhtä suuri kuin $\gcd[c, d]$, missä $0 \le a \le b < N$ ja $0 \le c \le d < N$, ja muulloin $0$.

Osatehtävät

Osatehtävä 1 (37 pistettä)

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

Osatehtävä 2 (24 pistettä)

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

Osatehtävä 3 (39 pistettä)

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

Esimerkit

Esimerkki vuorovaikutuksesta jonolle $S = [12, 4, 16, 2, 2, 20]$ on:

Huomautus

Esimerkki Ghițăn haluaman kaltaisesta puusta edelliselle esimerkille on: