I am thinking of an integer ~X~ between ~1~ and ~N~. You can guess up to 30 numbers to discover ~X~. Each time, I will tell you if your guess is too low, too high, or just right.

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 30 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.

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.