「他是名震四方的法外之徒， 英勇無畏的 Andrii Popa。

日夜兼程策馬馳騁， 他在大道上收取買路財， 全國上下的捕快們， 都在拼命望風而逃。」

—— “Andrii Popa”，Phoenix

Ghiță 有一個索引從 $0$ 開始、包含 $N$ 個正整數權重的序列 $S$。由於他是喀爾巴阡山脈之王，他想要構造一棵節點編號為 $0, 1, \ldots, N - 1$ 的二元樹，使得：

• 這棵樹的中序走訪按編號遞增的順序給出所有節點。一棵二元樹的中序走訪由以根節點的左子節點為根的子樹的中序走訪（如果該左子節點存在），接著是根節點的編號，再接著是以根節點的右子節點為根的子樹的中序走訪（如果該右子節點存在）依序組成。
• 如果節點 $x$ 是節點 $y$ 的父節點，那麼 $S_x$ 整除 $S_y$。

我們回顧一下，二元樹是一種樹狀資料結構，其中每個節點至多有兩個子節點，分別稱為左子節點和右子節點。

不幸的是，著名的法外之徒 Andrii Popa 偷走了序列 $S$，Ghiță 無法再直接存取它。借助先進的技術（他的手機），對於 $S$ 的任意兩個連續子序列 $[a, b]$ 和 $[c, d]$，他可以得知 $\gcd[a, b]$ 是否等於 $\gcd[c, d]$，其中 $\gcd[x, y]$ 是 $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$ 的最大公因數。不幸的是，這項技術相當昂貴——如果 Ghiță 使用它的次數超過 $Q$ 次，他就不得不支付巨額罰款。請幫助他使用這項技術至多 $Q$ 次來構造所需的樹。保證這一定是可行的。任何合法的解都將被接受。

互動

參賽者應當引入標頭檔 popa.h（C / C++）或實作 popa.pas（Pascal）。參賽者需要實作以下函式：

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

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

該函式應當回傳樹的根節點，並將 $\text{Left}_i$ 和 $\text{Right}_i$ 分別設為節點 $i$ 的左子節點和右子節點。如果節點 $i$ 沒有左子節點，則 $\text{Left}_i$ 應當為 $-1$。如果節點 $i$ 沒有右子節點，則 $\text{Right}_i$ 應當為 $-1$。Left 和 Right 指向兩個已經配置好、大小恰好為 $N$ 的陣列。

在單次執行過程中，solve 函式至多會被呼叫 $5$ 次。我們建議謹慎使用全域變數。

參賽者可以使用以下函式：

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

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

若且唯若 $\gcd[a, b]$ 等於 $\gcd[c, d]$（其中 $0 \le a \le b < N$ 且 $0 \le c \le d < N$）時，該函式回傳 $1$，否則回傳 $0$。

子任務

子任務 1（37 分）

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

子任務 2（24 分）

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

子任務 3（39 分）

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

範例

對於 $S = [12, 4, 16, 2, 2, 20]$ 的一個互動範例如下：

說明

對於上述範例，Ghiță 想要的那類樹的一個範例如下：