I am thinking of an integer ~X~ between ~1~ and ~N~. You can guess up to 40 numbers to discover ~X~. Each time, I will tell you if your guess is too low, too high, or just right. However, the game ends in your loss if I respond too low 10 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 40 guesses to the judge.

For each guess, output the guessed number ~Y~ on a new line, and flush standard output. The judge will respond with either too low, too high, or just right.

• 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
too low
>>>2
too low
>>>4
too high
>>>3
just right

Notes

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

Problem Source: 2006 Chinese Winter Training Camp Report.