Problem C
Age Guessing Dilemma

Tyko has made a new friend, Jonis, and is curious about his age. But when Tyko asks, Jonis tells him to guess instead! As a help, Jonis will reveal if his real age is higher or lower after each guess Tyko makes.

Tyko is tired of these games and wants to guess correctly as quickly as possible, but he knows that some people are sensitive about their age. In fact, Jonis is particularly sensitive about looking older than he is. Therefore, if Tyko’s guess is too high, Jonis gets $B$ times as upset as when the guess is too low!

Thankfully, Tyko comes prepared with an earpiece so you can feed him the best guesses! By looking at Jonis, he can see that his age is between $1$ and $10^{9}$, inclusive, so that should give you a good starting point!

Interaction

This problem is interactive.

Write a program that feeds Tyko with guesses for Jonis’s age. Jonis’s real age, $J$, is between $1$ and $10^{9}$, inclusive.

The input starts with the value of $B$ ($1 \le B \le 20$). Then, each time you make a guess $G$, the judge responds with one of the following:

• higher if $G < J$. You incur a penalty of $1$.

• lower if $G > J$. You incur a penalty of $B$.

• correct if $G = J$.

A testcase counts as successful if you guessed the correct age without exceeding penalty $27B+14$.

Make sure to flush the output after each guess. After receiving the correct response, your program must exit normally to be accepted.

Scoring

There are two groups of test cases.

10

792

higher

999

lower

990

higher

995

correct