CF1934C.Find a Mine

This is an interactive problem.

You are given a grid with $n$ rows and $m$ columns. The coordinates $(x, y)$ represent the cell on the grid, where $x$ ($1 \leq x \leq n$) is the row number counting from the top and $y$ ($1 \leq y \leq m$) is the column number counting from the left. It is guaranteed that there are exactly $2$ mines in the grid at distinct cells, denoted as $(x_1, y_1)$ and $(x_2, y_2)$. You are allowed to make no more than $4$ queries to the interactor, and after these queries, you need to provide the location of one of the mines.

In each query, you can choose any grid cell $(x, y)$, and in return, you will receive the minimum Manhattan distance from both the mines to the chosen cell, i.e., you will receive the value $\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)$.

Your task is to determine the location of one of the mines after making the queries.

这是一个交互式问题。

你将得到一个 $n$ 行 $m$ 列的网格。坐标 $(x, y)$ 表示网格中的一个格子，其中 $x$（$1 \leq x \leq n$）是从上往下数的行号，$y$（$1 \leq y \leq m$）是从左往右数的列号。保证网格中恰好有 $2$ 颗地雷，分别位于互异的格子 $(x_1, y_1)$ 和 $(x_2, y_2)$。你最多可向交互器发起 $4$ 次查询；在这些查询之后，你需要给出其中一颗地雷的位置。

每次查询时，你可以任选一个网格格子 $(x, y)$；作为回应，你将收到两颗地雷到该格子的曼哈顿距离的最小值，即你将收到数值 $\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)$。

你的任务是在完成查询后，确定其中一颗地雷的位置。

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \leq t \leq 3 \cdot 10^{3}$) — the number of test cases.

The only line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^{8}$, $2 \leq m \leq 10^{8}$) — the number of rows and columns.

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 3 \cdot 10^{3}$）—— 测试用例的数量。

每个测试用例仅有一行，包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^{8}$，$2 \leq m \leq 10^{8}$）—— 行数和列数。

In the first test case, we start by querying the upper-left corner $(1, 1)$ and get the result $3$, which means that there is a mine on the counter diagonal, and there is no mine above it.

In the image below, each cell contains a number indicating the distance to the blue cell. The green cells are candidates to contain the nearest mine.

Then we ask three cells on that diagonal, and at the last query, we get the result $0$, which means that a mine is found at the position $(2, 3)$.

The second mine was located at the position $(3, 2)$.

In the second test case, we start by asking the lower-right corner $(5, 5)$, and get the result $1$, which means that one of the two neighbours contains a mine, let's call it mine $1$.

Then we ask cell $(2, 2)$. We can see that these green cells don't intersect with the green cells from the first query, so they contain the other mine, let's call it mine $2$.

Query $3$ is cell $(3, 3)$. These cells contain mine $1$, but we still don't know where exactly. Nevertheless, we can determine that the only possible cell for mine $2$ is $(1, 1)$, because all other candidates are at a distance closer than $3$ for this query.

在第一个测试用例中，我们首先查询左上角单元格 $(1, 1)$，得到结果 $3$，这意味着蓝色单元格所在的反对角线上存在一颗地雷，且该地雷上方没有地雷。

下图中，每个单元格内的数字表示其到蓝色单元格的曼哈顿距离。绿色单元格是可能包含最近地雷的候选位置。

接着，我们在该反对角线上依次查询三个单元格；在最后一次查询时，得到结果 $0$，表明在位置 $(2, 3)$ 找到了一颗地雷。

第二颗地雷位于位置 $(3, 2)$。

在第二个测试用例中，我们首先查询右下角单元格 $(5, 5)$，得到结果 $1$，这意味着其两个相邻单元格中有一个含有地雷，我们称其为地雷 $1$。

然后我们查询单元格 $(2, 2)$。可以看出，这些绿色单元格与第一次查询所得的绿色单元格互不相交，因此它们包含另一颗地雷，我们称其为地雷 $2$。

第三次查询的单元格是 $(3, 3)$。这些绿色单元格包含地雷 $1$，但我们仍无法确定其确切位置。然而，我们可以推断出地雷 $2$ 的唯一可能位置是 $(1, 1)$，因为其余所有候选位置在本次查询中到 $(3, 3)$ 的距离均小于 $3$。