I. Guess Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
A one-line solution: Without loss of generality, assume $$$x \lt y$$$. Take $$$a=y-x, b=0$$$, and you can get $$$\gcd(y, y) = y$$$.
—Mouthwatering Chicken

This is an interactive problem.

The interactor has two hidden integers $$$x$$$ and $$$y$$$ ($$$0 \leq x, y \lt 2^{60}$$$), and your task is to determine the values of $$$x$$$ and $$$y$$$ by making queries.

In each query, you can choose two integers $$$a$$$ and $$$b$$$ ($$$0 \leq a, b \lt 2^{61}$$$), and the interactor will return the value of $$$\gcd(x+a, y+b)$$$ $$$^{\dagger}$$$.

For each pair of hidden integers $$$x$$$ and $$$y$$$, you must determine their values within $$$200$$$ queries.

$$$^{\dagger}$$$ $$$\gcd(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$. For example, $$$\gcd(6, 8) = 2, \gcd(7, 5) = 1$$$. The values of $$$\gcd(x, 0)$$$ and $$$\gcd(0, x)$$$ are defined as $$$x$$$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 100$$$).

Interaction

To make a query, you should output "? a b" ($$$0 \leq a, b \lt 2^{61}$$$). After flushing your output, your program should read a line containing the value of $$$\gcd(x+a, y+b)$$$. You can make at most $$$200$$$ queries.

To report your guess, you should output "! x y" ($$$0 \leq x, y \lt 2^{60}$$$), indicating your guess for $$$x$$$ and $$$y$$$. After flushing your output, you should proceed to the next test case immediately. If you have completed all test cases, your program should exit immediately.

To flush your output, you can use:

  • fflush(stdout) (if you use printf) or cout.flush() (if you use cout) in C and C++.
  • System.out.flush() in Java and Kotlin.
  • stdout.flush() in Python.
Example
Input
2

3

2

3

10

7
Output

? 2 0

? 1 1

! 1 3
? 3 1

? 10 5

? 7 2

! 0 5