interactive-gcd-xor

Interaction

You may ask queries of the following type: '? $c$ ', $1 \leq c \leq 1 0^{9}$ 1\le c\le 10^{9}. The interactor will then return $g cd (a, c) \oplus g cd (b, c)$ \gcd(a,c) \oplus \gcd(b,c).

Once you have determined the answer $x$ , output it by printing '! $x$ '.

Do not forget to flush the output after each query and after giving the answer using fflush(stdout) in C++ or sys.stdout.flush() in python.

Examples

Example 1

Loading

Note

The hidden integers in the sample are 4 and 6.

After the first query, the interactor returns $g cd (4, 1) \oplus g cd (6, 1) = 1 \oplus 1 = 0$ \gcd(4,1) \oplus \gcd(6,1)=1 \oplus 1 =0.

In the third query, the program than asks ? 67 to which the interactor returns 0.

Finally after all queries are made, the program correctly outputs 12, since $lcm (6, 4) = 12$ \mathrm{lcm}(6,4)=12.

Scoring

Subtask $1$ : $(a = 1)$ (a=1) ( $50$ points)

Subtask $2$ : $(a = k^{x}, b = k^{y})$ (a=k^x, b=k^y) for some $k, x, y \in Z$ k,x,y \in \mathbb{Z}, $k \geq 1$ k\ge 1, $x, y \geq 0$ x,y \ge 0 ( $100$ points)

Subtask $3$ : No additional constraints ( $250$ points)