题目背景

翻译自 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

题目描述

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ță 国王想要的树形态如下图所示。

输入格式

见「交互」。

输出格式

见「交互」。

提示

数据范围