Ghiță 有一个包含 $N$ 个正整数权值的 0-索引序列 $S$。作为喀尔巴阡山脉的国王，他想要构建一棵节点索引为 $0, 1, \dots, 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}, \dots, 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;

该函数应返回树的根节点，并将 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);

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

当且仅当 $\gcd[a, b]$ 等于 $\gcd[c, d]$ 时，该函数返回 1，否则返回 0。其中 $0 \le a \le b < N$ 且 $0 \le c \le d < N$。

子任务

• 子任务 1（37 分）：$N = 100$，$Q = 10\,000$
• 子任务 2（24 分）：$N = 1\,000$，$Q = 20\,000$
• 子任务 3（39 分）：$N = 1\,000$，$Q = 2\,000$

样例

输入格式 1

solve(6, Left, Right)
query(0, 1, 3, 5)
query(4, 5, 1, 3)

输出格式 1

0
1

说明

solve 返回 3。 Left 指向 [-1, 0, -1, 1, -1, -1]。 Right 指向 [-1, 2, -1, 4, 5, -1]。

附注

上述样例中 Ghiță 想要的树的一个示例如下：

上述样例中 Ghiță 想要的树的一个示例