CF1627B.Not Sitting

Rahul and Tina are looking forward to starting their new year at college. As they enter their new classroom, they observe the seats of students are arranged in a $n \times m$ grid. The seat in row $r$ and column $c$ is denoted by $(r, c)$, and the distance between two seats $(a,b)$ and $(c,d)$ is $|a-c| + |b-d|$.

As the class president, Tina has access to exactly $k$ buckets of pink paint. The following process occurs.

• First, Tina chooses exactly $k$ seats in the classroom to paint with pink paint. One bucket of paint can paint exactly one seat.
• After Tina has painted $k$ seats in the previous step, Rahul chooses where he sits. He will not choose a seat that has been painted pink due to his hatred of the colour pink.
• After Rahul has chosen his seat, Tina chooses a seat for herself. She can choose any of the seats, painted or not, other than the one chosen by Rahul.

Rahul wants to choose a seat such that he sits as close to Tina as possible. However, Tina wants to sit as far away from Rahul as possible due to some complicated relationship history that we couldn't fit into the statement!

Now, Rahul wonders for $k = 0, 1, \dots, n \cdot m - 1$, if Tina has $k$ buckets of paint, how close can Rahul sit to Tina, if both Rahul and Tina are aware of each other's intentions and they both act as strategically as possible? Please help satisfy Rahul's curiosity!

拉胡尔和蒂娜期待着在大学开启崭新的一年。当他们走进新教室时，发现学生的座位被排列成一个 $n \times m$ 的网格。第 $r$ 行、第 $c$ 列的座位记为 $(r, c)$，而两个座位 $(a,b)$ 与 $(c,d)$ 之间的距离定义为 $|a-c| + |b-d|$。

作为班长，蒂娜恰好拥有 $k$ 桶粉色油漆。整个过程如下：

• 首先，蒂娜从教室中恰好选择 $k$ 个座位涂上粉色油漆；每桶油漆恰好可涂一个座位。
• 在蒂娜完成上述 $k$ 个座位的粉刷后，拉胡尔选择自己的座位；由于他极度厌恶粉色，他绝不会选择已被涂成粉色的座位。
• 在拉胡尔选定座位后，蒂娜再为自己选择一个座位；她可选择任意一个座位（无论是否被涂成粉色），但不能选择拉胡尔已选的那个座位。

拉胡尔希望选择一个座位，使自己与蒂娜之间的距离尽可能小；然而，蒂娜却希望与拉胡尔之间的距离尽可能大——这源于一段我们无法在题面中详述的复杂情感纠葛！

现在，拉胡尔想知道：当 $k = 0, 1, \dots, n \cdot m - 1$ 时，若蒂娜拥有 $k$ 桶油漆，在双方均充分了解彼此意图且均采取最优策略的前提下，拉胡尔最终能离蒂娜最近达到多远的距离？请帮助满足拉胡尔的好奇心！

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $m$ ($2 \leq n \cdot m \leq 10^5$) — the number of rows and columns of seats in the classroom.

The sum of $n \cdot m$ across all test cases does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5 \cdot 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$、$m$（$2 \leq n \cdot m \leq 10^5$），分别表示教室中座位的行数和列数。

所有测试用例中 $n \cdot m$ 的总和不超过 $10^5$。

For each test case, output $n \cdot m$ ordered integers — the distance between Rahul and Tina if both of them act optimally for every $k \in [0, n \cdot m - 1]$.

对于每个测试用例，输出 $n \cdot m$ 个有序整数——即对每个 $k \in [0, n \cdot m - 1]$，当 Rahul 和 Tina 均采取最优策略时，他们之间的距离。

One possible sequence of choices for the first testcase where Tina has $k=3$ buckets of paints is as follows.

Tina paints the seats at positions $(1, 2)$, $(2, 2)$, $(3, 2)$ with pink paint. Rahul chooses the seat at $(3, 1)$ after which Tina chooses to sit at $(1, 3)$.

Therefore, the distance between Tina and Rahul is $|3-1| + |1-3| = 4$, and we can prove that this is indeed the minimum possible distance under the given constraints. There may be other choices of seats which lead to the same answer as well.

For $k=0$ in the first test case, Rahul can decide to sit at $(2, 2)$ and Tina can decide to sit at $(4, 3)$ so the distance between them would be $|2 - 4| + |2 - 3| = 3$.

Below are pictorial representations of the $k=3$ and $k=0$ cases for the first test case.

A possible seating arrangement for $k=3$. A possible seating arrangement for $k=0$.

第一个测试用例中，当蒂娜拥有 $k=3$ 桶颜料时，一种可能的选择序列如下：

蒂娜使用粉色颜料为位置 $(1, 2)$、$(2, 2)$、$(3, 2)$ 的座位上色。随后拉胡尔选择坐在 $(3, 1)$，蒂娜则选择坐在 $(1, 3)$。

因此，蒂娜与拉胡尔之间的距离为 $|3-1| + |1-3| = 4$，且可以证明：在给定约束条件下，该距离确实为可能的最小值。也存在其他座位选择方式，可得到相同的答案。

在第一个测试用例中，当 $k=0$ 时，拉胡尔可选择坐在 $(2, 2)$，蒂娜可选择坐在 $(4, 3)$，此时他们之间的距离为 $|2 - 4| + |2 - 3| = 3$。

以下是第一个测试用例中 $k=3$ 和 $k=0$ 情况的图示表示：

$k=3$ 时的一种可能就座安排。
$k=0$ 时的一种可能就座安排。