Wesley's template has everything, except for good support for interactive problems and fast arbitrary precision integer arithmetic. For now.

Wesley is playing a game against Lesley. They are both standing in front of a pile of ~N~ pebbles and will alternate turns. On a person's turn, they may take ~2^X~ pebbles from the pile for some nonnegative integer ~X~. The person who takes the last pebble from the pile wins. Wesley gets to choose whether he goes first or second. Help Wesley win.

Constraints

~N \le 10^{1000}~

Input

This is an interactive problem. You will first read a single integer ~N~. After that, you will either print 1 to say that Wesley wants to go first or you will print 2 to say that Wesley wants to go second.

On Wesley's turn, you must print an integer ~Y~ indicating that Wesley will take ~Y~ pebbles. On Lesley's turn, you will read in an integer ~Y~ indicating that Lesley took ~Y~ pebbles. In both cases, ~Y~ must be a power of two.

Make sure to flush your output. Terminate with exit code 0 when the game is over, otherwise your program may get an undefined verdict.

Sample Interaction Details

<<< indicates values that you read in, >>> indicates values that you print out.

Sample Interaction 1

3 <<<
>>> 2
1 <<<
>>> 2

Sample Interaction 2

4 <<<
>>> 1
>>> 4