23406번 - Polynomial in a Black Box 다국어인터랙티브

문제

This is an interactive problem.

Alice has a black box which works with integers modulo $m = 10^{9} + 7$. If a user types a number $x$ on the keyboard of the box, the screen shows the number equal to the value of the polynomial $p (x) = (a_{d} x^{d} + a_{d - 1} x^{d - 1} + \ldots + a_{1} x^{1} + a_{0}) \bmod m$. The degree $d$ of the polynomial is unknown, as are its coefficients $a_{i}$. It is only known that 0ドル \le d \le 10$ and $a_d \ne 0$.

Alice can type several numbers $x$ and learn the values of the polynomial for these numbers. Help her find the degree $d$ of the polynomial. She can input an $x$ at most $d + 3$ times.

입력

출력

제한

인터랙션 프로토콜

To learn the value of the polynomial for number $x,ドル print a line of the form "ask $x$" (0ドル \le x < 10^{9} + 7$). As a result, you will get a line with the value $p (x),ドル or, if you asked more than $d + 3$ such questions, you will get the number $-1$ instead of the value, and evaluation of your solution will terminate.

To give the answer, print a line of the form "degree $d$". After that, terminate your solution gracefully.

After printing each line, flush the output buffer, or you will get the outcome Idleness Limit Exceeded: this can be done by calling, for example, fflush (stdout) in C or C++, System.out.flush () in Java, flush (output) in Pascal, or sys.stdout.flush () in Python.

노트

In each test, the degree and the coefficients of the polynomial $p (x)$ are chosen and fixed in advance.

In the example, which is also the first test in the testing system, $p (x) = x^2 + 1,000円,000円,005円$. All other tests were created as follows: first, the degree $d$ was chosen (0ドル \le d \le 10$), and after that, one of the polynomials of such degree was chosen as $p (x)$ uniformly at random.