CF2135B For the Champion

本题为交互题。 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$ 个锚点的坐标。 保证所有锚点的坐标各不相同。

（本题输出与交互过程有关，无具体静态输出格式。详见题目交互协议。）

以下是样例的交互过程说明： 有 $2$ 组测试数据。 1. 第一组有 $1$ 个锚点。 0 0 锚点坐标为 $(0, 0)$。 评测程序选定机器人的初始坐标为 $(100, 99)$。 ? D 99 机器人向下移动 $99$ 单位，当前位置 $(100, 0)$。评测程序返回 $|100-0|+|0-0|=100$。 ? L 101 机器人向左移动 $101$ 单位，当前位置 $(-1, 0)$。评测程序返回 $|(-1)-0|+|0-0|=1$。 ! 100 99 机器人确定初始坐标为 $(100, 99)$ 并上报。答案正确，进入下一组测试数据。 2. 第二组有 $4$ 个锚点。 1 1 2 2 3 3 -1 -1 四个锚点的坐标分别为 $(1,1)$，$(2,2)$，$(3,3)$，$(-1,-1)$。 评测程序选定机器人初始坐标为 $(-1, 0)$。 ? L 0 机器人向左移动 $0$ 单位，实时坐标为 $(-1, 0)$。评测程序返回 $|(-1)-(-1)|+|0-(-1)|=1$。 ? U 1 机器人向上移动 $1$ 单位，当前位置 $(-1, 1)$。返回 $|(-1)-(-1)|+|1-(-1)|=2$。 ? R 2 机器人向右移动 $2$ 单位，当前位置 $(1, 1)$。返回 $|1-1|+|1-1|=0$。 ! -1 0 机器人确定初始坐标为 $(-1, 0)$ 并上报。答案正确，交互结束。 由 ChatGPT 5 翻译