这是一个交互式问题。在打印每行后，你必须立即执行 flush 操作。例如，在 C++ 中你应该使用 fflush(stdout) 或 cout.flush()，在 Java 或 Kotlin 中使用 System.out.flush()，在 Python 中使用 sys.stdout.flush()。

给你一个圆，圆上有 $10^9$ 个点。这些点均匀分布，并按顺时针方向从 $0$ 到 $10^9 - 1$ 进行编号。

我们将点 $i$ 和 $j$ 之间的距离定义为 $d(i, j) = \min(|i - j|, 10^9 - |i - j|)$，即这两个点将圆分成的两条弧中较短的那条弧的长度。

在这些点中，系统选择并隐藏了恰好三个不同的点。你的任务是确定这些隐藏点之间的弧长。

你可以进行如下形式的询问：

• 你可以选择任意点 $x \in [0, 10^9 - 1]$ 并对其进行询问；
• 系统将计算 $x$ 到每个隐藏点的距离，并返回其中最小的非零距离。

你最多可以进行 300 次询问，但有一个限制：每进行三次询问后，圆都会被循环移动一个随机整数。换句话说，在回答完第 3 次、第 6 次、第 9 次等询问后，系统会选择一个随机数 $s$，并将每个隐藏点 $i$ 移动到 $i' = (i + s) \bmod 10^9$。

在每个测试用例中，这些点在最开始是固定好的，但每次移动都是随机的。对于每次移动，每个整数 $s \in [0, 10^9 - 1]$ 都是等概率选择的。

交互格式

首先，评测程序会打印一行，包含一个整数 $t$ ($1 \le t \le 10$) —— 测试用例的数量。

要进行询问，你应该按照以下格式打印一行：

• ? x ($0 \le x < 10^9$) —— 你要询问的点。

作为回应，评测程序将打印一行，包含一个整数 —— $[d_1, d_2, d_3]$ 中的最小非零整数，其中 $d_i$ 是 $x$ 到第 $i$ 个隐藏点的距离。

要给出答案，你应该按照以下格式打印一行：

• ! a b c ($1 \le a, b, c \le 10^9$) —— 其中 $a, b$ 和 $c$ 是隐藏点之间的弧长。

你可以以任意顺序输出弧长。但是，请注意，弧长并不总是与题目中定义的点对之间的距离一致。换句话说，必须满足 $a + b + c = 10^9$。

打印答案后，你应该继续处理下一个测试用例（如果这是最后一个测试用例，则终止程序）。

在打印任何内容后，请不要忘记刷新输出缓冲区。否则，你可能会得到 Idleness Limit Exceeded（空闲超限）的结果。

样例

输入样例 1

2
1
1
1
218790401
2
200000000
150000000

输出样例 1

? 0
? 1
? 2
? 0
? 781209599
! 2 1 999999997
? 500000000
? 150000000
! 300000000 400000000 300000000

说明

请注意，样例中的空行仅为了便于阅读 —— 交互程序不会添加空行。

在第一个测试用例中，隐藏的点为 $[1, 2, 4]$。在第三次询问后，它们被移动了 $781\,209\,595$（该值仅作为示例）。

在第二个测试用例中，隐藏的点为 $[0, 300\,000\,000, 700\,000\,000]$。