CF1155E.Guess the Root

Jury picked a polynomial $f(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \dots + a_k \cdot x^k$. $k \le 10$ and all $a_i$ are integer numbers and $0 \le a_i \lt 10^6 + 3$. It's guaranteed that there is at least one $i$ such that $a_i \gt 0$.

Now jury wants you to find such an integer $x_0$ that $f(x_0) \equiv 0 \mod (10^6 + 3)$ or report that there is not such $x_0$.

You can ask no more than $50$ queries: you ask value $x_q$ and jury tells you value $f(x_q) \mod (10^6 + 3)$.

Note that printing the answer doesn't count as a query.

Interaction

To ask a question, print "? $x_q$" $(0 \le x_q \lt 10^6 + 3)$. The judge will respond with a single integer $f(x_q) \mod (10^6 + 3)$. If you ever get a result of $−1$ (because you printed an invalid query), exit immediately to avoid getting other verdicts.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

When you are ready to answer, print "! $x_0$" where $x_0$ is the answer or $-1$ if there is no such $x_0$.

You can ask at most $50$ questions per test case.

Hack Format

To hack, use the following format.

The only line should contain $11$ integers $a_0, a_1, \dots, a_{10}$ ($0 \le a_i \lt 10^6 + 3$, $\max\limits_{0 \le i \le 10}{a_i} \gt 0$) — corresponding coefficients of the polynomial.

评委选定一个多项式 $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 \lt 10^6 + 3$。保证至少存在一个下标 $i$ 使得 $a_i \gt 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 \lt 10^6 + 3$）。评测系统将返回一个整数 $f(x_q) \mod (10^6 + 3)$。若你收到结果 $-1$（因输出了非法查询），请立即退出程序，以免获得其他错误提示。

每次输出查询后，务必输出换行符并刷新输出缓冲区；否则将得到 “Idleness limit exceeded” 判定。具体操作如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请参阅相应文档。

当你准备好回答时，请输出 "! $x_0$"，其中 $x_0$ 即所求答案；若不存在满足条件的 $x_0$，则输出 -1。

每个测试用例中最多允许 $50$ 次询问。

Hack 格式

用于 Hack 的输入格式如下：

仅一行，包含 $11$ 个整数 $a_0, a_1, \dots, a_{10}$（满足 $0 \le a_i \lt 10^6 + 3$，且 $\max\limits_{0 \le i \le 10}{a_i} \gt 0$），表示该多项式的各项系数。

The polynomial in the first sample is $1000002 + x^2$.

The polynomial in the second sample is $1 + x^2$.

第一个样例中的多项式为 $1000002 + x^2$。

第二个样例中的多项式为 $1 + x^2$。