Description
One day, Lizard Tom ran into his idol, Wizard Tom! Just thinking about Wizard Tom making endless popcorn made Lizard Tom drool.
"I have an integer in my mind, ranging from to . If you can guess it, I'll magically make some popcorn for you!" Wizard Tom said with a grin. Although it sounded like a boring and childish game, Lizard Tom decided to play along just for the popcorn.
"I guess 1!", "I guess 2!", "I guess 3!"... The "smart" Lizard Tom had just learned how to count, and it was obvious that he intended to guess every single number from to sequentially.
If Lizard Tom keeps playing like this, the sun will set before he gets his treats. You decide to help Tom come up with a more reasonable strategy:
- Calculate a number , where . represents the greatest integer less than or equal to
- Tell Tom to guess for this round.
- If m = t, it means Tom has successfully guessed the number, and the guessing ends, skip the remaining steps.
- Check if holds true: if it is true, update to ; otherwise, update to .
- If still holds, take the updated and and go back to Step 1.
Lizard! Lizard! Lizard!
Looking at Tom, who is now distracted and playing with buttons, you realize he hasn't even learned how to add and subtract. Therefore, please write a program to execute this strategy and decide what number Tom should guess:
For each round Tom makes a guess , output Guess m and a newline. When the search ends, after outputting the final Guess t, output an additional line Take y times to find t, where is the total number of guesses Tom made, and terminate the search.
In fact, we call this algorithm "binary search", and it'll come in handy in future homeworks
Input
The input is given from Standard Input in the following format:
Output
For each round Tom makes a guess , output Guess m and a newline. When the search ends, after outputting the final Guess t, output an additional line Take y times to find t, where is the total number of guesses Tom made.