题目背景

Upd on 2024/10/22 加入一组 Hack 数据（#13）

题目描述

这是一道交互题。

Lloyd 有一个随机数生成器，对于随机种子 $s$ 和生成器类型 $t$，它第 $x$ 次（$x<p$）生成的随机数是：

$$r_{s,t}(x)=\begin{cases}s^x\bmod p&t=1\\x^s\bmod p&t=2\end{cases} $$

其中 $p$ 是一个固定素数。$0\le s<p-1$。

现在给定 $p,t$。已知随机数生成器在你询问之前已经生成过若干随机数，而在你生成随机数的时候不会有任何其他随机数生成访问（也就是你生成的是一段连续的随机数）。你每次可以调用随机数生成器来获取一个随机数，并且在若干次调用之后找出随机数种子 $s$ 的值。保证有解且 5 次询问后一定能得到唯一的解。

---

实现细节

本题采用 IO 交互模式。

第一行输入两个正整数 $t,p$。

接下来，可以向交互库发送以下两种操作：

• ?，表示调用一次随机数生成器，随即你可以从标准输入中读入随机数生成器生成的数值。
• ! s，报告你发现的 $s$。

发送 ! 操作后你应该立即结束程序。另外在每一次操作后都需要清空缓冲区。评分方式见数据范围部分。

如果你的操作不符合交互格式可能出现不可预料的结果。保证在交互次数不超过 19930（也就是至少可以获得 1 分）时交互库的运行时间不超过 100ms。对于 19930 之上的交互次数不保证交互库运行时间。

输入格式

见题目描述中实现细节部分。

输出格式

见题目描述中实现细节部分。

1 10007

4960

?

! 114

2 10007

4960

6980

?

?

! 514

提示

样例解释

样例仅供参考，不一定具有实际逻辑。

第一组样例：$p=10007$，$s=114$，在询问之前生成过 $513$ 次随机数。

第二组样例：$p=10007$，$s=514$，在询问之前生成过 $113$ 次随机数。

---

数据范围

本题采用捆绑测试。（Subtask 分数为 Subtask 内各测试点分数之最小值）

• Subtask 1 (20pts)：$t=1$。
• Subtask 2 (20pts)：$p\le 10^3$。
• Subtask 3 (60pts)：无特殊限制。

对于全部数据，$2\le p\le2\times10^6$ 且 $p$ 是素数，$t\in\{1,2\}$，保证有解。

对于每个测试点，如果你向交互库发送了 $c$ 次 ? 操作，那么你可以得到的分数由如下表达式给出：

$$\mathrm{score}=\begin{cases}100&c\le 5\\\max\{0,100-\lceil10\ln(c)\rceil\}&\text{otherwise.}\end{cases} $$