Scales#13077

Scales

0.5 seconds
256 megabytes

The jury has old scales and two secret integers and , where 0 \le a, b < 2^n, and the number is known to you. Your task is to find both secret numbers.

The scales are a bit unusual. You can give the jury two integers and (0 \le x, y < 2^n). Then the jury places the number a \oplus x on the left pan, and the number b \oplus y on the right pan, and reports which pan is heavier, or that the scales are balanced. In other words, you learn the result of comparing a \oplus x with b \oplus y. Here denotes the bitwise exclusive OR (XOR).

You may use the scales no more than times.

Input

The first line contains a single integer (2 \le n \le 60).

Interaction

To perform a weighing, output a line ? x y with two integers and (0 \le x, y < 2^n). In response, the jury will output a line with a single character:

  • <, if a \oplus x < b \oplus y;

  • =, if a \oplus x = b \oplus y;

  • >, if a \oplus x > b \oplus y.

When you have determined the secret numbers, output a line ! a b with the numbers and and terminate the program. This line is not counted as a weighing.

After outputting each line, make sure to output a newline character and flush the output buffer (for example, fflush(stdout) or cout.flush() in C++, sys.stdout.flush() in Python, System.out.flush() in Java). Otherwise, you may receive a “Time Limit Exceeded” verdict. If you perform more than weighings, or a weighing with numbers outside the allowed bounds, or output a line in an incorrect format, you will receive a “Wrong Answer” verdict.

The jury may be adaptive: the numbers and are not fixed in advance and may depend on your weighings. However, at every moment there exists at least one pair that is consistent with all the answers given so far. Therefore, output the answer only when the pair is uniquely determined: if there exists another pair that is also consistent with all the answers, the jury may consider that pair to be the secret one, and your answer will be judged incorrect.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the examples, the input column shows the lines output by the jury, and the output column shows the lines output by your program, in the order in which the exchange takes place. Blank lines are added only for column alignment; they are not part of the interaction.

In the first example, n = 3, and the secret numbers are a = 5 and b = 3.

  • ? 0 0 compares a = 5 with b = 3, the answer is >;

  • ? 4 0 compares 5 \oplus 4 = 1 with , the answer is <;

  • ? 0 4 compares with 3 \oplus 4 = 7, the answer is <;

  • ? 4 2 compares 5 \oplus 4 with 3 \oplus 2, that is with , the answer is =;

  • ? 4 3 compares 5 \oplus 4 with 3 \oplus 3, that is with , the answer is >.

To give the answer, the program outputs ! 5 3. Five weighings were used, which is within the limit of .

In the second example, n = 2, a = 1, b = 3.

  • ? 0 0, the answer is <;

  • ? 0 2 compares with b \oplus 2, the answer is =;

  • ? 0 3 compares with b \oplus 3, the answer is >.

Three weighings were used, which is within the limit of .