Bob was bored, so he challenged Alice to a guessing game. Bob starts with an integer $x$, which Alice must try to guess. Every time that Alice guesses an integer $y$, Bob reports the distance $|x-y|$ between $x$ and $y$. Then, Bob performs the following modification to $x$:

• First he sets $x$ to the midpoint of $x$ and $y$, rounding to the integer closest to the value of $y$
• Then, he tosses a fair coin, and if it lands tails, he reflects $x$ over $y$

Alice would like you to help her come up with a strategy that minimizes the number of guesses that she has to make. To verify that the strategy that you came up with is reasonable, Alice will check that every guess that you make is between $A$ and $B$ (inclusive), where $A$ is the minimum value that $x$ can take given the current set of information, and $B$ is the maximum value.

Constraints

The initial value of $x$ satisfies $1\le x\le {10}^9$.

You are allowed to make at most $30$ guesses.

Interaction

This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.

You will start the interaction by proceeding with your guesses. Each guess should be formatted as y followed by a \n character. In response, you will be given the current value of $|x-y|$ on its own line. If $|x-y|=0$, then you have correctly guessed $x$ and you should immediately terminate your program. Otherwise, $x$ will be modified as stated above, and you should continue with the interaction.

If at any point you attempt an invalid question (such as an invalid output format or a prohibited value of $y$), or you exceed the limit of $30$ guesses, the interactor will respond with $-1$. You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Scoring

If you fail to guess $x$ in at most $30$ guesses, or at any point output an invalid guess, then you will receive $0$ points. Otherwise, you will receive $50\mathrm{\%}$ of the points for a correct guess, and $100\mathrm{\%}$ of the points if you guessed $x$ in at most $10$ guesses.

Sample Interaction

>>> denotes your output. Do not print this out.

>>> 3
2
>>> 4
0

Sample Explanation

The initial value of $x$ is $1$, and the value after the first guess is $4$. Therefore, the second guess is correct, and interaction terminates.