陪审团选择了一个多项式 $$$f(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \dots + a_k \cdot x^k$$$。 $$$k \le 10$$$ 和所有 $$$a_i$$$ 都是整数,$$$0 \le a_i < 10^6 + 3$$$。保证至少有一个 $$$i$$$ 使得 $$$a_i > 0$$$。
现在陪审团希望你找到这样一个整数 $$$x_0$$$ 使得 $$$f(x_0) \equiv 0 \mod (10^6 + 3)$$$ 或报告不存在这样的 $$$x_0$$$。
您可以询问不超过 $$$50$$$ 查询:您询问值 $$$x_q$$$,陪审团告诉您值 $$$f(x_q) \mod (10^6 + 3)$$$。
请注意,打印答案不算作查询。
互动
要提出问题,请打印“? $$$x_q$$$”$$$(0 \le x_q < 10^6 + 3)$$$。法官将返回一个整数 $$$f(x_q) \mod (10^6 + 3)$$$。如果您得到 $$$−1$$$ 的结果(因为您打印了无效的查询),请立即退出以避免得到其他结论。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
当你准备好回答时,打印“!$$$x_0$$$”,其中$$$x_0$$$是答案,如果没有这样的$$$x_0$$$,则打印$$$-1$$$。
每个测试用例最多可以提出 $$$50$$$ 问题。
黑客格式
要破解,请使用以下格式。
唯一的一行应包含 $$$11$$$ 整数 $$$a_0, a_1, \dots, a_{10}$$$ ($$$0 \le a_i < 10^6 + 3$$$, $$$\max\limits_{0 \le i \le 10}{a_i} > 0$$$) — 多项式的相应系数。
示例
输入 #1
1000002 0
输出 #1
? 0 ? 1 ! 1
输入 #2
5 2 1
输出 #2
? 2 ? 1 ? 0 ! -1
注意
第一个样本中的多项式为 $$$1000002 + x^2$$$。
第二个样本中的多项式为 $$$1 + x^2$$$。