CF2118E.Grid Coloring

有一个 $n \times m$ 的网格，初始时每个格子都是白色的。你需要依次为所有格子染色。每当你染色一个格子时，所有距离它最远的已染色格子会受到一次惩罚。请你给出一种染色顺序，使得没有任何格子的惩罚次数超过 $3$。

注意，$n$ 和 $m$ 都是奇数。

本题使用的距离度量为“棋盘距离”（Chebyshev 距离），在判定距离相等时，使用“曼哈顿距离”（Taxicab 距离）来决定优先级。具体来说，若有格子 $(x_2, y_2)$ 和 $(x_3, y_3)$，对于格子 $(x_1, y_1)$，如果满足下列条件之一，则认为 $(x_2, y_2)$ 比 $(x_3, y_3)$ 更远：

• $\max\big(\lvert x_1 - x_2 \rvert, \lvert y_1 - y_2 \rvert\big) > \max\big(\lvert x_1 - x_3 \rvert, \lvert y_1 - y_3 \rvert\big)$
• $\max\big(\lvert x_1 - x_2 \rvert, \lvert y_1 - y_2 \rvert\big) = \max\big(\lvert x_1 - x_3 \rvert, \lvert y_1 - y_3 \rvert\big)$ 且 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert > \lvert x_1 - x_3 \rvert + \lvert y_1 - y_3 \rvert$

可以证明，至少存在一种可行解。

上图展示了在 $5 \times 5$ 网格中染色中心格子后各格子的惩罚变化。数字表示各格子的惩罚次数。

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

每个测试用例的第一行包含两个奇数整数 $n$ 和 $m$（$1 \le n, m \le 4999$），分别表示行数和列数。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $5000$。

对于每个测试用例，输出 $n \cdot m$ 行，第 $i$ 行输出你选择的第 $i$ 个染色格子的坐标。若有多种方案，输出任意一种均可。

样例输出中的空行仅为增强可读性，你不需要输出空行。

在第一个测试用例中，网格可以按如下方式染色：

数字表示各格子的惩罚次数。

由 ChatGPT 4.1 翻译