“Dia seorang penjahat dan dia terkenal, Andrii Popa sang pemberani.

Siang dan malam dia berkuda, Dia memungut upetinya dari jalan utama Dan di seluruh penjuru negeri Para penangkap pencuri berlari kabur secepat yang mereka bisa”

— “Andrii Popa”, Phoenix

Ghiță memiliki barisan $S$ berindeks-$0$ yang terdiri dari $N$ bobot bilangan bulat positif. Karena dia adalah raja Pegunungan Carpathia, dia ingin membentuk sebuah pohon biner yang simpul-simpulnya memiliki indeks $0, 1, \ldots, N - 1$ sedemikian sehingga:

• Penelusuran inorder (inorder traversal) dari pohon tersebut menghasilkan simpul-simpul dalam urutan indeks yang menaik. Penelusuran inorder dari sebuah pohon biner dibentuk dari penelusuran inorder upapohon yang berakar pada anak kiri dari akar (jika anak tersebut ada), diikuti oleh indeks akar, lalu diikuti oleh penelusuran inorder upapohon yang berakar pada anak kanan dari akar (jika anak tersebut ada).
• Jika simpul $x$ adalah induk dari simpul $y$, maka $S_x$ habis membagi $S_y$.

Kita ingat kembali bahwa pohon biner adalah struktur data pohon yang setiap simpulnya memiliki paling banyak dua anak, yang disebut anak kiri dan anak kanan.

Sayangnya, penjahat terkenal Andrii Popa telah mencuri barisan $S$, sehingga Ghiță tidak dapat lagi mengaksesnya secara langsung. Menggunakan teknologi canggih (telepon genggamnya), untuk setiap dua subbarisan kontigu $[a, b]$ dan $[c, d]$ dari $S$, dia dapat mengetahui apakah $\gcd[a, b]$ sama dengan $\gcd[c, d]$, dengan $\gcd[x, y]$ adalah faktor persekutuan terbesar dari $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Sayangnya, teknologi ini cukup mahal — jika Ghiță menggunakannya lebih dari $Q$ kali, dia harus membayar denda yang besar. Bantulah dia dengan menggunakan teknologi tersebut paling banyak $Q$ kali untuk membangun pohon yang diinginkan. Dijamin bahwa hal ini mungkin dilakukan. Solusi valid apa pun akan diterima.

Interaksi

Peserta harus menyertakan header popa.h (C / C++) atau mengimplementasikan popa.pas (Pascal). Peserta perlu mengimplementasikan fungsi berikut:

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

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

Fungsi ini harus mengembalikan akar dari pohon, serta mengatur $\text{Left}_i$ dan $\text{Right}_i$ masing-masing menjadi anak kiri dan anak kanan dari simpul $i$. Jika simpul $i$ tidak memiliki anak kiri, maka $\text{Left}_i$ harus bernilai $-1$. Jika simpul $i$ tidak memiliki anak kanan, maka $\text{Right}_i$ harus bernilai $-1$. Left dan Right menunjuk ke dua larik berukuran tepat $N$ yang sudah dialokasikan.

Fungsi solve dapat dipanggil paling banyak $5$ kali selama satu kali eksekusi. Kami menyarankan agar berhati-hati dalam menggunakan variabel global.

Peserta dapat menggunakan fungsi berikut:

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

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

Fungsi ini akan mengembalikan $1$ jika dan hanya jika $\gcd[a, b]$ sama dengan $\gcd[c, d]$, dengan $0 \le a \le b < N$ dan $0 \le c \le d < N$, serta mengembalikan $0$ jika sebaliknya.

Subsoal

Subsoal 1 (37 poin)

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

Subsoal 2 (24 poin)

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

Subsoal 3 (39 poin)

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

Contoh

Contoh interaksi untuk $S = [12, 4, 16, 2, 2, 20]$ adalah:

Catatan

Contoh pohon seperti yang diinginkan Ghiță untuk contoh sebelumnya adalah: