I am thinking of an integer ~X~ between ~1~ and ~N~. You can guess up to 50 numbers to discover ~X~. Each time, I will tell you if your previous guess is too low, too high, or just right. However, the game ends in your loss if I respond too low 15 or more times.

Can you determine ~X~?

Input Specification

The first line of input will contain a single integer, ~N~ (~1\leq N\leq 10^9~).

Output Specification

For each guess, output an integer ~Y~, (~1\leq Y\leq N~).

Interaction

The judge will start by printing the integer ~N~.

You may make up to 50 guesses to the judge.

For each guess, output the guessed number ~Y~ on a new line, and flush standard output. Starting from the second guess, the judge will respond with either too low, too high, or just right, based on the result of your previous guess.

• Your program will be judged as correct if the judge outputs just right.
• If you exceed the allowed number of queries, the judge will output query limit exceeded and your program will receive the verdict Wrong Answer.
• If you exceed the allowed number of too low responses, the judge will output too many too low and your program will receive the verdict Wrong Answer.

In all cases, your program should terminate immediately.

Sample Interaction

>>> denotes your output; don't actually print this out.

5
>>>1
>>>5
too low
>>>3
too high
>>>4
just right

Explanation for Sample Interaction

The grader has ~X = 3~.

• The user guesses 1, and then 5. As ~1 < 3~, the judge responds too low.
• The user guesses 3; the previous guess is 5. As ~5 > 1~, the judge responds too high.
• The user guesses 4; the previous guess is 3. As ~3 = 3~, the judge responds just right.

Notes

The grader is adaptive, i.e. it will attempt to screw you over.

Problem Source: 2006 Chinese Winter Training Camp Report.