P15425 Nobody Tells


**这是一道交互题。** 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 解释 交互库获得的数据为 $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