Santa's Guessing Game

Worth 4 point(s) - Runtime Limit: 5 seconds


So you ended up on Santa's naughty list. Well luckily for you Santa has a way to get back on the nice list. All you have to do is guess what number he is thinking of from 0 to \(n\). To make it more fair, you can guess a number, and he will tell you if it's higher or lower than the number he is thinking of. But you only have \(\log_2 n\) guesses before you're out of luck.

Can you outsmart Santa?

Write a program that can guess a number from 0 to \(n\) in \(\log_2 n\) attempts.

Input and Output

The format for this problem is different than the others. Your program will be talking to another program (representing Santa). You can ask Santa if the number he is thinking of is something, and he will respond with either LOWER if his number is lower than yours, HIGHER is his number is higher than yours, and CORRECT if you guessed the number right.

Here is how it will work:
Santa will tell you \(n\) where \(0 ≤ n ≤ 100,000,000\).


Then you can make your guess of what number he is thinking of


Then Santa will respond with either HIGHER, LOWER, or CORRECT


Then you can make another guess


...and so on and so forth

If you can guess Santa's number in the correct amount of attempts, you can get back on the nice list (and solve this problem).

NOTE: Do not use kb.hasNext() in your input loop, instead use kb.hasNextLine()

Sample Input


Sample Output