这是一个交互式问题。
评测系统选择了 $T \le 10$ 个整数,范围在 $1$ 到 $10^{18}$(包含边界)。你需要逐一猜出这些数字。
假设评测系统选择的数字为 $x$。你可以重复询问一个 $1$ 到 $10^{18}$ 之间的整数 $y$,系统会告知你 $x + y$ 是素数还是合数。当你猜出该数字时,请将其输出,然后开始猜测下一个数字。
除了样例测试外,所有 $T$ 个数字都是从区间 $[1, 10^{18}]$ 中独立且均匀随机选择的。你需要使用总共不超过 $8750$ 次询问来猜出所有数字。
交互协议
首先,读取一行包含整数 $T$ 的内容:评测系统选择的整数个数($1 \le T \le 10$)。评测系统选择了 $T$ 个秘密整数 $x_1, \dots, x_T$,你需要依次猜出它们($1 \le x_i \le 10^{18}$)。
假设你正在尝试猜测数字 $x_i$。要进行一次询问,请输出一行格式为 “? y” 的内容($1 \le y \le 10^{18}$)。然后读取下一行:
- 如果 $x_i + y$ 是素数,你将读取到单词 “Prime”;
- 如果 $x_i + y$ 是合数,你将读取到单词 “Composite”;
- 如果你进行了无效的询问(在整个程序运行期间第 $8751$ 次询问;或格式不符合要求;或 $y$ 不是规定范围内的正整数),你将读取到单词 “Busted”。
当你认为你知道 $x_i = z$ 时,请输出一行格式为 “! z” 的内容($1 \le z \le 10^{18}$)。该行不计入询问次数限制。然后读取下一行:
- 如果确实 $x_i = z$,你将读取到单词 “Correct”。如果 $i = T$,程序应终止;否则,继续猜测数字 $x_{i+1}$。
- 如果 $x_i \neq z$ 或者你违反了输出格式,你将读取到单词 “Busted”。
读取到 “Busted” 后,你的程序必须立即终止以获得 Wrong Answer 判决。否则,判决结果将不可预测。
样例
样例输入 1
1 Composite Prime Prime Prime Correct
样例输出 1
? 6 ? 5 ? 3 ? 1 ! 2
说明
共有 $30$ 组测试数据。在第 $i$ 组测试中,$T = \min\{i, 10\}$。在每组测试中,选定的 $T$ 个整数是预先固定的:对于每个解法的每次运行,它们都是相同的,并且在交互过程中不会改变。