有一个 $$$n\times m$$$ 网格,每个单元格最初都是白色的。您必须将所有单元格一一着色。为单元格着色后,所有 彩色细胞 离它最远的人会受到惩罚。找到一个着色顺序,其中没有单元格的处罚超过 $$$3$$$。
请注意 $$$n$$$ 和 $$$m$$$ 都是奇数。
使用的距离度量是棋盘距离,而我们用曼哈顿距离来确定单元格之间的关系。形式上,如果满足以下条件之一,则单元格 $$$(x_2, y_2)$$$ 与单元格 $$$(x_1, y_1)$$$ 的距离比 $$$(x_3, y_3)$$$ 更远:
- $$$\max\big(\lvert x_1 - x_2 \rvert, \lvert y_1 - y_2 \rvert\big) \gt \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 \gt \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$$$ 个单元格的坐标。如果有多个解决方案,请打印其中任何一个。
示例输出中的空行只是为了提高可读性。您不需要打印它们。
示例
输入复制
33 31 11 5
输出复制
2 1 2 3 2 2 1 1 3 2 3 3 3 1 1 3 1 2 1 1 1 2 1 4 1 5 1 1 1 3
注意
在第一个测试用例中,网格可以按如下方式着色:
数字表示单元格的惩罚。