#214928. [ICPC 2022 Yokohama R] Interactive Number Guessing

This is an interactive problem.

Your task is to write a program that guesses a secret number through repetitive queries and responses. The secret number is a non-negative integer less than .

Let be the secret number. In a query, you specify a non-negative integer . In response to this, the digit sum of will be returned. Here, the digit sum of a number means the sum of all the digits in its decimal notation. For example, the digit sum of 4096 is .

Interaction

You should start with sending a query to the standard output and receiving the response from the standard input. This interaction can be repeated a number of times. When you have become confident of your guess through these interactions, you can send your answer.

A query should be in the following format, followed by a newline.

Here, is an integer between and , inclusive. In response to this query, the digit sum of , where is the secret number, is sent back to the standard input, followed by a newline.

You should send your answer to the standard output in the following format, followed by a newline.

Here, is the secret number you have identified, an integer between and , inclusive.

You can send the answer only once, so you have to become sure of your guess through repeated interactions before sending the answer. However, you can send no more than queries, and thus you have to choose your queries cleverly. After sending the answer, your program should terminate without any extra output.

Notes on interactive judging

When your output violates any of the conditions above (invalid format, or being out of the range, too many queries, an extra output after sending your answer, and so on), your submission will be judged as a wrong answer. As some environments require flushing the output buffers, make sure that your outputs are actually sent. Otherwise, your outputs will never reach the judge.

样例输入 1

15

1

样例输出 1

query 3

query 25

answer 75

In this example, the secret number is . In response to the first query, is returned because and its digit sum is . After the second response, you can conclude that the only possible secret number is .