这是一个交互式问题。

RiOI 团队正在举办一场机器人锦标赛！

这次，你的机器人被传送到一个带有笛卡尔坐标系的无限二维平面上。平面上有 $n$ 个锚点，第 $i$ 个锚点的坐标为 $(x_i, y_i)$（$-10^9 \le x_i, y_i \le 10^9$）。机器人在被传送到平面后，评审团会立即将这些信息提供给机器人。但是，机器人一开始并不知道自己的初始坐标。

为了测试机器人的智商，RiOI 团队设计了一个有趣的游戏。你的机器人需要通过执行以下操作来找出初始坐标 $(X, Y)$（$-10^9 \le X, Y \le 10^9$）。

在一步操作中，假设机器人当前位置为 $(a, b)$，机器人可以选择一个非负整数 $k$（$0 \le k \le 10^9$），并执行以下四种类型操作中的一种：

• 向上移动 $k$ 个单位，即机器人移动到 $(a, b + k)$；
• 向下移动 $k$ 个单位，即机器人移动到 $(a, b - k)$；
• 向左移动 $k$ 个单位，即机器人移动到 $(a - k, b)$；
• 向右移动 $k$ 个单位，即机器人移动到 $(a + k, b)$。

每次移动后，评审团会给出机器人当前位置与任意锚点之间的最小曼哈顿距离。更正式地说，假设移动后机器人的坐标为 $(c, d)$，评审团将输出

$$\min_{1 \le i \le n} (|x_i - c| + |y_i - d|)$$

为了赢得奖品，你必须证明你的机器人具有高智商。因此，你需要为机器人编写一个程序，使其在不超过 $10$ 步操作内找出初始坐标 $(X, Y)$。

---

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）——锚点的数量。

接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$）——第 $i$ 个锚点的坐标。

保证所有锚点的坐标两两不同。

---

交互格式

对于每个测试用例，首先读取 $n$ 和锚点的坐标。然后你可以进行最多 $10$ 次操作。

要进行一次操作，你应该按以下格式之一输出一行：

• ? U k —— 向上移动 $k$ 个单位；
• ? D k —— 向下移动 $k$ 个单位；
• ? L k —— 向左移动 $k$ 个单位；
• ? R k —— 向右移动 $k$ 个单位。

你需要保证 $0 \le k \le 10^9$。

每次操作结束后，评审团会输出一个整数 $s$——机器人当前位置与任意锚点之间的最小曼哈顿距离。

要报告你已找到机器人的初始坐标，请按以下格式输出一行：

• ! X Y —— 机器人的初始坐标为 $(X, Y)$。

输出答案不算在 $10$ 次操作之内。

之后，继续处理下一个测试用例，或者如果是最后一个测试用例则终止程序。

假设机器人的初始坐标为 $(X, Y)$，保证 $-10^9 \le X, Y \le 10^9$。

---

注意事项

每次输出查询后，不要忘记输出换行并刷新输出缓冲区。否则你会收到“Idleness limit exceeded” verdict。

如果在交互过程中的任何时刻你读到了 $-1$ 而不是有效数据，你的程序必须立即退出。这意味着你的程序可能因为无效查询或其他错误而收到“Wrong answer”。未能退出可能导致任意 verdict，因为你的程序会继续从已关闭的流中读取。

本题的交互器不是自适应的。换句话说，机器人的初始坐标在交互过程中不会改变。

---

黑客（Hack）格式

要进行 hack，请使用以下格式：

第一行包含一个整数 $t$（$1 \le t \le 100$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）——锚点的数量。

接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$）——第 $i$ 个锚点的坐标。

接下来一行包含两个整数 $X$ 和 $Y$（$-10^9 \le X, Y \le 10^9$）——机器人的初始坐标。

---

示例

输入

2
1
0 0

100

1

4
1 1
2 2
3 3
-1 -1

1

2

0

输出

? D 99

? L 101

! 100 99





? L 0

? U 1

? R 2

! -1 0

---

示例说明

解决方案	评审团	解释
2		本测试包含 $2$ 个测试用例。
1		第一个测试用例有 $1$ 个锚点。
0 0		唯一锚点的坐标为 $(0, 0)$。
	评审团选择 $(100, 99)$ 作为机器人的初始坐标。
? D 99	100	机器人向下移动 $99$ 单位，当前位置为 $(100, 0)$。评审团输出 $|100-0| + |0-0| = 100$。
? L 101	1	机器人向左移动 $101$ 单位，当前位置为 $(-1, 0)$。评审团输出 $|-1-0| + |0-0| = 1$。
! 100 99		机器人确定了初始坐标并输出答案。输出正确，评审团继续下一个测试用例。
4		第二个测试用例有 $4$ 个锚点。
1 1		第一个锚点坐标 $(1, 1)$。
2 2		第二个锚点坐标 $(2, 2)$。
3 3		第三个锚点坐标 $(3, 3)$。
-1 -1		第四个锚点坐标 $(-1, -1)$。
	评审团选择 $(-1, 0)$ 作为机器人的初始坐标。
? L 0	1	机器人向左移动 $0$ 单位，即保持原位。评审团输出 $|-1-(-1)| + |0-(-1)| = 1$。可以证明这是机器人与任意锚点的最小曼哈顿距离。
? U 1	2	机器人向上移动 $1$ 单位，当前位置为 $(-1, 1)$。评审团输出 $|-1-(-1)| + |1-(-1)| = 2$。
? R 2	0	机器人向右移动 $2$ 单位，当前位置为 $(1, 1)$。评审团输出 $|1-1| + |1-1| = 0$。
! -1 0		机器人确定了初始坐标并输出答案。由于输出正确且没有更多测试用例，评审团和程序退出。