题目描述
翻译自 BalkanOI 2018 Day2 T2「Popa」

Ghiță 有一个下标从 $0$ 开始的正整数序列 $S$。他想要构造一个节点编号为 $0,1,\ldots ,N-1$ 的二叉树，满足：

1. 树的中序遍历按节点编号升序排列；
2. 如果 $x$ 是 $y$ 节点的父亲，那么 $S_x$ 整除 $S_y$。

序列 $S$ 被 Andrii Popa 偷走了，但 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$ 的最大公因数。

他最多只能使用 $Q$ 次询问，请帮他在不超过限制的情况下构建出二叉树。保证这是可能的。

交互方式
本题只支持 C++ 语言使用函数交互，其他语言可以通过 IO 交互来完成本题。

选手应包含头文件 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$。

使用 IO 交互
你的程序可以使用标准输入输出与交互器交互，格式如下。

在程序的开始，你应从标准输入读取一个整数 $T$，表示测试数据组数。

接下来开始进行每组数据的交互。在每组数据交互开始，你应从标准输入读取一个整数 $N$，意义同题目描述。接下来，如需调用 query 函数，你的程序应先输出一个 ?，后输出四个整数 $a,b,c,d$，意义同「交互」一节中函数的四个参数。整数与 ?，整数与整数之间用一个空格分隔；如果 solve 函数返回，你的程序应先输出形如 ! r 的一行，$r$ 表示 solve 函数的返回值。接下来输出两行长度为 $N$ 的整数数列，第一行按顺序输出 Left 数组中的元素，第二行按顺序输出 Right 数组中的元素。任意两个整数之间用一个空格隔开。

请不要忘记对于每行，都要输出换行符，并刷新标准输出缓冲区。

样例
例如 $S=[12, 4, 16, 2, 2, 20]$，一组交互过程如下：

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

评分