Description

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。

选手需实现如下函数：

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$ 次。我们建议谨慎使用全局变量。

选手可以调用如下函数（注意，选手须在代码中声明此函数）：

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]$，一组交互过程如下：

样例中，Ghiță 国王想要的树形态如下图所示。

Input Format

见「交互」。

Output Format

见「交互」。

Hint

数据范围