这是一个交互问题!
Timofey 正在编写一项名为“Capture the Flag”(简称 CTF)的竞赛。他还剩下一项任务,涉及入侵安全系统。整个系统基于多项式哈希$$$^{\text{*}}$$$。
Timofey 可以向系统输入一个由小写拉丁字母组成的字符串,系统将返回其多项式哈希。为了破解系统,Timofey 需要找到系统使用的多项式哈希参数($$$p$$$ 和 $$$m$$$)。
Timofey 的时间不多了,所以他只能进行 $$$3$$$ 查询。帮助他解决任务。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。
保证系统使用的$$$p$$$和$$$m$$$满足条件:$$$26 < p \leq 50$$$ 和 $$$p + 1 < m \leq 2 \cdot 10^9$$$。
互动
要向系统查询,输出 ? $$$s$$$,其中 $$$s$$$ 是长度不超过 $$$50$$$ 个字符的字符串,您想知道其哈希值。作为对该查询的响应,您将收到字符串 $$$s$$$ 的多项式哈希。
要输出答案,请输出! $$$p$$$ $$$m$$$,其中 $$$p$$$ 是哈希的基数,$$$m$$$ 是模数。之后,立即进行下一个测试用例。
您必须进行不超过 $$$3$$$ 的查询?,否则您将得到错误答案的结论。
输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到超出空闲限制的判决。要刷新缓冲区,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
示例
输入 #1
1 32 28
输出 #1
? aa ? yb ! 31 59
注意
第一个查询的答案是 $$$(ord(a) \cdot 31^0 + ord(a) \cdot 31^1) \mod 59 = (1 + 1 \cdot 31) \mod 59 = 32$$$。
第二个查询的答案是 $$$(ord(y) \cdot 31^0 + ord(b) \cdot 31^1) \mod 59 = (25 + 2 \cdot 31) \mod 59 = 28$$$。