26230번 - Guess the modulo 다국어인터랙티브

문제

Fimka Sobak, unlike Ellochka the Cannibal, was reputed to be a cultured girl. In addition to her favorite smart buzzword, the $\ldots$-ality, she learned a remarkably entertaining game, "Guess the modulo".

The game is played in the following way. There are two players: the leader and the player. The leader initially thinks of two numbers: $N$ --- the number of numbers to be summed and $M$ --- the modulo. The leader tells the player the number $N,ドル and the player must guess the number $M$. Moreover, the leader thinks of an array of $(N-1)$ numbers and tells it to the player.

During the game the player tells the leader numbers to get more information. Every time the player says a number, the leader:

1. appends it to the end of his array,
2. calculate $S$ --- the sum of the last $N$ numbers in the array by the modulo $M,ドル
3. appends $S$ to the end of the array and
4. tells $S$ to the player.

As soon as the player guesses the value of the modulo $M,ドル he or she informs the leader.

It is known that the modulo $M$ lies within the range between 2ドル$ and 10ドル^9,ドル inclusively.

인터랙션

This problem is interactive, and instead of file input-output you'll have to work with a special program --- an interactor. Interacting with the program is performed through the standard input-output streams.

First you will be given the number $N$ and the first $(N-1)$ numbers of the array. Next, your programs will be sending queries. Each query for an addition of a number to the array will retrieve a new sum modulo according to the game rules. After the query guessing the modulo the player's solution must terminate.

If you can't guess the modulo or guess wrong, you will get the verdict \textsf{Wrong Answer}.

The number of player's queries, including the final modulo-guessing query, must not be greater than 10ドル^3$. If you exceed the limit of the number of queries, you will get the verdict Wrong Answer.

입력

The first line of the input stream contains a single integer $N$ (2ドル \le N \le 100$). The following line contains $(N-1)$ space-separated integers ranging from 0ドル$ to 10ドル^9$ inclusively.

The following lines of the input stream contain answers to questions. Each answer is the sum of the last $N$ elements of its array by modulo $M$.

출력

You should print the queries and the player's answer into the standard output.

Player query format: "? p", p --- the number added by the player to the array. The number $p$ must be integer and must lie within the range from 0ドル$ to 10ドル^9$ inclusively.

Player answer format: "! M", M --- the modulo in question.

Make sure that each query ends with a line break and that you flush the output stream buffer (the flush command of the language). Otherwise the solution may get the verdict Deadlock.

제한

힌트