「彼は無法者にして名高き男、 勇敢なる Andrii Popa。

昼も夜も馬を駆り、 街道で年貢を取り立てる。 国中のどこでも 盗賊捕りたちは全力で逃げ出している」

— “Andrii Popa”, Phoenix

Ghiță は $N$ 個の正の整数の重みからなる $0$ 始まりの列 $S$ を持っています。彼はカルパティア山脈の王であるため、頂点の番号が $0, 1, \ldots, N - 1$ である二分木であって、次の条件を満たすものを構築したいと考えています。

• 木の通りがけ順（中間順）走査によって、頂点が番号の昇順に得られる。二分木の通りがけ順走査は、根の左の子を根とする部分木の通りがけ順走査（左の子が存在する場合）、根の番号、根の右の子を根とする部分木の通りがけ順走査（右の子が存在する場合）をこの順に並べることで構成される。
• 頂点 $x$ が頂点 $y$ の親であるならば、$S_x$ は $S_y$ を割り切る。

二分木とは、各頂点が最大で $2$ 個の子（それぞれ左の子、右の子と呼ばれる）を持つ木構造のデータ構造であることを思い出しましょう。

残念なことに、名高い無法者 Andrii Popa が列 $S$ を盗んでしまったため、Ghiță はもはや $S$ に直接アクセスすることができません。高度な技術（彼の携帯電話）を使うことで、彼は $S$ の任意の $2$ つの連続部分列 $[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$ の $2$ つの配列を指しています。

関数 solve は $1$ 回の実行中に最大 $5$ 回呼び出される可能性があります。グローバル変数の扱いには注意することをお勧めします。

競技者は次の関数を使用することができます。

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

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

この関数は、$0 \le a \le b < N$ かつ $0 \le c \le d < N$ のもとで $\gcd[a, b]$ が $\gcd[c, d]$ に等しいとき、かつそのときに限り $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ță が求めている種類の木の一例は次の通りです。