说明

这是一道交互题。

Coola 有两个数 $p,q$，还有一个质数 $M$，我们用如下方法生成一个序列 $\{f_i\}$：

$$\begin{cases} f_{0}=1\\ f_{1}=p\\ f_{i}=(pf_{i-1}+qf_{i-2})\bmod M,&i>1 \end{cases}$$

交互库会给定你 $M$ 和一个参数 $L$，你最多可以向交互库查询 $3$ 次：

• 给出一个 $L\le i\le M^2$，交互库告诉你 $f_i$ 的值。

你的任务是，在最多 $3$ 次查询之后猜出 $(p,q)$ 的值。特别地，你可以同时猜测两对 $(p,q)$，详见交互细节。

交互细节

本题包含多组测试。

在输入数据的第一行，交互库会给你的程序一个数 $T$，表示该测试点的测试数据组数。

对于每组测试数据：

交互库会获得该测试数据的 $(p,q)$。这同时也说明交互库是非自适应性的。

第一行，交互库向你的程序输入两个数 $M,L$，表示模数与询问限制。

对于每次询问，你需要输出 ? i，表示查询 $f_i$ 的值。

正常情况下，交互库会向你输入一个 $[0,M)$ 中的整数，表示你查询的 $f_i$。

若发生以下情况，交互库会立刻终止交互并强制退出程序，该测试点将被判定为不通过：

• 询问次数超过 $3$。
• $i$ 不在 $L\le i\le M^2$ 的范围中。

在你猜出可能的 $(p,q)$ 后，你需要输出 ! p1 q1 p2 q2，表示你猜测的两对 $(p,q)$ 分别为 $(p_1,q_1)$ 与 $(p_2,q_2)$。此操作不计入询问的 $3$ 次操作中。特别地，你需要保证四个数都在 $[1,M)$ 的范围中，否则交互库会立刻终止交互并强制退出程序，该测试点将被判定为不通过。

若两对答案中存在一对与交互库得到的值相同，则通过了该测试数据，否则不通过，且交互库会立刻终止交互并强制退出程序。

若你通过了一个测试点中的所有测试数据，该测试点将被判定为通过。

1
5 1

3

1

? 1

? 2

! 3 2 1 1

提示

样例 #1 解释

交互库获得的数据为 $p=3,q=2,M=5,L=1$。

第一次交互，你的程序通过 $\texttt{? 1}$ 询问 $f_1$ 的值，显然 $f_1=p=3$，因此交互库向你的程序输入 $3$。

第二次交互，你的程序通过 $\texttt{? 2}$ 询问 $f_2$ 的值，$f_2=(pf_1+qf_0)\bmod 5=11\bmod 5=1$。因此交互库向你的程序输入 $1$。

由于 $f_2=(p^2+q)\bmod 5$，而我们知道 $p=3$，可以解出 $q=2$。所以你已经用两次询问确定了答案，可以输出 $\texttt{! 3 2 1 1}$。由于第一对答案正确，第二对答案是多少就无关紧要了，所以 $\texttt{! 3 2 4 3}$ 也是可行的输出，但 $\texttt{! 3 2 1 5}$ 或 $\texttt{! 3 2 0 4}$ 都不是，因为要保证四个数都在 $[1,5)$ 的范围内。

数据范围

本题开启捆绑测试。

对于 $100\%$ 的数据，$1\le T\le 10^5$。$10^6\le M\le 10^9$，保证 $M$ 是质数。$0\le L\le 5\times 10^5$。

交互库不是自适应的，$1\le p,q<M$。

子任务	特殊性质	得分
1	$L=1$	$2$
2	$T\le 500$ 且 $L=15$	$10$
3	$M=10^6+3$	$20$
4	$T\le 10$ 且 $M\le 5\times 10^6$
5	无	$48$

后记

:::epigraph[——《Nobody Tells》] 过程中指路的灯火
你是其中一盏 :::