Interactive Number

Limits: 1 sec., 256 MiB

This is an interactive problem. Make sure to flush the output evey time you print a line.

Your task is to guess the number \(n\) between 1 and \(10^9\), inclusive.

To make a guess, print a line with a number that should be an integer between 1 and \(10^9\), inclusive. After that, read a response line containing one of the following characters:

• means your guess is less than \(n\);

• means your guess is greater than \(n\);

• means your guess is correct, please exit your solution.

You can make up to 47 guesses. Note that if a guess is invalid, your solution will immediatedy get the Wrong answer verdict.

Constraints

\(1 \le n \le 10^9.\)

Notes

If \(n=47\), the input and output might look like this:

>

>

<

=

100

50

40

47