„Jest banitą i jest sławny, Andrii Popa odważny.

Dniem i nocą pędzi konno, Pobiera haracz na głównym trakcie, A w całym kraju Łapacze złodziei uciekają, ile sił w nogach”

— „Andrii Popa”, Phoenix

Ghiță ma indeksowany od $0$ ciąg $S$ złożony z $N$ dodatnich całkowitych wag. Ponieważ jest królem Karpat, chce skonstruować drzewo binarne, którego wierzchołki mają indeksy $0, 1, \ldots, N - 1$, takie że:

• Przejście drzewa w porządku inorder daje wierzchołki w kolejności rosnących indeksów. Przejście inorder drzewa binarnego składa się z przejścia inorder poddrzewa zaczepionego w lewym synu korzenia (jeśli ten syn istnieje), następnie indeksu korzenia, a następnie przejścia inorder poddrzewa zaczepionego w prawym synu korzenia (jeśli ten syn istnieje).
• Jeśli wierzchołek $x$ jest ojcem wierzchołka $y$, to $S_x$ dzieli $S_y$.

Przypominamy, że drzewo binarne to drzewiasta struktura danych, w której każdy wierzchołek ma co najwyżej dwóch synów, nazywanych lewym synem i prawym synem.

Niestety słynny banita Andrii Popa ukradł ciąg $S$ i Ghiță nie ma już do niego bezpośredniego dostępu. Korzystając z zaawansowanej technologii (swojego telefonu komórkowego), może on dla dowolnych dwóch spójnych podciągów $[a, b]$ oraz $[c, d]$ ciągu $S$ sprawdzić, czy $\gcd[a, b]$ jest równe $\gcd[c, d]$, gdzie $\gcd[x, y]$ oznacza największy wspólny dzielnik liczb $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Niestety technologia ta jest dość kosztowna — jeśli Ghiță użyje jej więcej niż $Q$ razy, będzie musiał zapłacić wysoką grzywnę. Pomóż mu, używając tej technologii co najwyżej $Q$ razy, aby zbudować żądane drzewo. Gwarantujemy, że jest to możliwe. Każde poprawne rozwiązanie zostanie zaakceptowane.

Interakcja

Zawodnik powinien dołączyć plik nagłówkowy popa.h (C / C++) lub zaimplementować moduł popa.pas (Pascal). Zawodnik musi zaimplementować następującą funkcję:

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

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

Funkcja ta powinna zwrócić korzeń drzewa oraz ustawić $\text{Left}_i$ i $\text{Right}_i$ odpowiednio na lewego i prawego syna wierzchołka $i$. Jeśli wierzchołek $i$ nie ma lewego syna, to $\text{Left}_i$ powinno wynosić $-1$. Jeśli wierzchołek $i$ nie ma prawego syna, to $\text{Right}_i$ powinno wynosić $-1$. Wskaźniki Left oraz Right wskazują na dwie już zaalokowane tablice o rozmiarze dokładnie $N$.

Funkcja solve może zostać wywołana co najwyżej $5$ razy podczas jednego uruchomienia programu. Zalecamy ostrożność przy używaniu zmiennych globalnych.

Zawodnik może korzystać z następującej funkcji:

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

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

Funkcja ta zwróci $1$ wtedy i tylko wtedy, gdy $\gcd[a, b]$ jest równe $\gcd[c, d]$, gdzie $0 \le a \le b < N$ oraz $0 \le c \le d < N$, a w przeciwnym wypadku zwróci $0$.

Podzadania

Podzadanie 1 (37 punktów)

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

Podzadanie 2 (24 punkty)

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

Podzadanie 3 (39 punktów)

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

Przykład

Przykład interakcji dla $S = [12, 4, 16, 2, 2, 20]$ przedstawiono poniżej:

Uwagi

Przykładowe drzewo spełniające wymagania Ghițy dla powyższego przykładu: