Ghiță 有一个下标从 $0$ 开始的正整数序列 $S$。因为他是喀尔巴阡的国王，所以他想要构造一个节点编号为 $0,1,\ldots ,N-1$ 的二叉树，满足：
- 树的中序遍历按节点编号升序排列。二叉树的中序遍历由以根的左子节点（如果存在）为根形成的子树的中序遍历，根的节点编号和以根的右子节点（如果存在）为根形成的子树的中序遍历顺次连接组成。
- 如果 $x$ 是 $y$ 节点的父亲，那么 $S_x$ 整除 $S_y$。
二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。
不幸的是，著名的亡命之徒 Andrii Popa 偷走了序列 $S$，Ghiță 不能直接获取到。但对于任意两个连续的子序列 $[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$ 次的情况下构建出他想要的树。保证这是可能的。任何合法的构建方案都可以被接受。
### 交互
本题只支持 C++ 语言使用函数交互。选手代码并不需要也不能包含 `popa.h`。
选手需实现如下函数：
```cpp
int solve(int N, int* Left, int* Right);
```
函数需返回树的根节点，并且将 `Left[i]` 和 `Right[i]` 分别赋值为 $i$ 的左子节点和右子节点。如果节点 $i$ 没有左子节点，则 `Left[i]` 应被赋为 $-1$，如果节点 $i$ 没有右子节点，则 `Right[i]` 应被赋为 $-1$。`Left` 和 `Right` 分别指向两个空间已被分配好且长度恰好为 $N$ 的数组。
函数 `solve` 在一次运行中会被调用最多 $5$ 次。我们建议谨慎使用全局变量。
选手可以调用如下函数（注意，选手须在代码中声明此函数）：
```cpp
int query(int a, int b, int c, int d);
```
这个函数当且仅当 $\gcd[a,b]=\gcd[c,d]$ 时返回 $1$，其中 $0\le a\le b<n,0\le c\le d<N$，否则返回 $0$。
### 样例
例如 $S=[12, 4, 16, 2, 2, 20]$，一组交互过程如下：
| 调用 `solve` | 调用 `query` | 调用 `solve` 之后 |
| :-----------: | :-----------: | :-----------: |
| `solve(6, Left, Right)` | | |
| | `query(0, 1, 3, 5)` 返回 $0$ | |
| | `query(4, 5, 1, 3)` 返回 $1$ | |
| | | `solve` 返回值为 $3$；`Left` 指向 $[-1, 0, -1, 1, -1, -1]$；`Right` 指向 $[-1, 2, -1, 4, 5, -1]$ |
样例中，Ghiță 国王想要的树形态如下图所示。
## Input
见「交互」。
## Output
见「交互」。
[samples]
## Background
翻译自 BalkanOI 2018 Day2 T2「Popa」
> *"He's an outlaw and he's famous*
> *Andrii Popa the courageous.*
> *Day and night he rides,*
> *He takes his tribute from the main road*
> *And everywhere in the country*
> *The thief catchers are running away as fast as they can"*
>
> *\- ["Andrii Popa", Phoenix](https://music.163.com/song?id=508736536)*
## Note
### 数据范围
| 子任务编号 | 限制 | 分值 |
| :----------: | :----------: | :----------: |
| $1$ | $N=100,Q=10^4$ | $37$ |
| $2$ | $N=10^3,Q=2\times 10^4$ | $24$ |
| $3$ | $N=10^3,Q=2\times 10^3$ | $39$ |