Alice is doing the DMOPC! The third problem reads as follows:

Given are two non-negative integers ~X~ and ~Y~. In one operation, you can halve the value of either ~X~ or ~Y~, rounding down. Compute the minimum number of operations required to make ~X~ equal to ~Y~.

Of course, Alice is a legendary programmer, so she instantly produces a program that solves the problem correctly for all pairs ~(X, Y)~.

After the contest, while discussing the problem solutions with Alice, you somehow managed to leak to her the fact that you forgot the list of her ~N~ favourite numbers!

"Zettai ni yurusanai wa!" she shouts. Of course, you have no idea what she just said (why would you), but it sounded quite serious. After a bit of a back and forth quarrel, you've managed to reach a compromise based on the program Alice wrote for the third problem.

In short, Alice allows you to make at most ~32\,000~ guesses in total for her list of favourite numbers ~F_1, F_2, \dots, F_N~, which you recall to be integers in the range ~[0, 2^{60})~. You will guess her list in increasing order of index, starting with ~F_1~. In each guess, if you are currently guessing the ~i~-th number, you must tell her an integer ~G~ in the range ~[0, 2^{60})~ and she will respond with the integer her program returns after plugging in ~X = F_i~ and ~Y = G~.

Given these conditions, please redeem yourself by correctly guessing Alice's favourite numbers!

Constraints

~1 \le N \le 10^3~

~0 \le F_i < 2^{60}~

It is possible for the same number to appear more than once in Alice's list.

Subtask 1 [40%]

~1 \le N \le 500~

Subtask 2 [60%]

No additional constraints.

Interaction

At first, you should read in a line containing the integer ~N~.

You will then start the interaction by proceeding with your guesses, guessing ~F_1~ first. Each guess should be formatted as a single integer ~G~ followed by a \n character. If you are currently guessing the ~i~-th number, Alice will respond with a single line containing the integer her program returns after plugging in ~X = F_i~ and ~Y = G~.

If at any point Alice responds with ~0~, then you know that you have guessed the ~i~-th of her favourite numbers correctly and should move on to guessing the ~(i+1)~-th number. If she responds with ~0~ for the ~N~-th time, then you know that you have guessed her entire list correctly and should terminate your program to receive an Accepted verdict.

However, if at any point you exceed the limit of ~32\,000~ guesses, ~G~ is not an integer in the range ~[0, 2^{60})~, or your output is otherwise malformatted, Alice will respond with ~-1~. You should terminate your program at this point to avoid receiving an arbitrary verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

In this case, Alice's list of favourite numbers is ~[10, 24]~.

2
>>> 4
3
>>> 21
1
>>> 10
0
>>> 24
0

Explanation

For the first guess, Alice runs her program with ~X = 10~ and ~Y = 4~. Her program discovers that halving ~X~ twice (rounding down) giving ~X = 2~ and halving ~Y~ once giving ~Y = 2~ is the optimal solution to this case, equating ~X~ and ~Y~ in ~3~ operations total.

For the second guess, Alice runs her program with ~X = 10~ and ~Y = 21~. Halving ~Y~ once here (rounding down) gives ~X = Y~ in just ~1~ operation, so Alice responds with ~1~.

For the third guess, Alice runs her program with ~X = 10~ and ~Y = 10~. Clearly no operations are needed here, so she responds with ~0~. Now that you've correctly guessed the first number, you should move on to guessing the second one.

For the fourth guess, Alice runs her program with ~X = 24~ and ~Y = 24~. No operations are needed here either, so she responds with ~0~. Now that you've correctly guessed all the numbers in no more than ~32\,000~ guesses, you should terminate your program to receive an Accepted verdict.