2050志愿者正在组织“奔跑吧!追逐旭日”活动。 4月25日早上7点30分开始,跑者们将完成绕云栖小镇6公里的步道。
路径上有 $$$n+1$$$ 个检查站。它们的编号为 $$$0$$$、$$$1$$$、...、$$$n$$$。跑步者必须从检查点 $$$0$$$ 开始,并在检查点 $$$n$$$ 结束。没有检查点是可以跳过的——他必须从检查点 $$$0$$$ 跑到检查点 $$$1$$$,然后从检查点 $$$1$$$ 跑到检查点 $$$2$$$,依此类推。查看注释部分中的图片以进行澄清。
在任意两个相邻的检查点之间,有 $$$m$$$ 条不同的路径可供选择。对于任何$$$1\le i\le n$$$,从检查点$$$i-1$$$跑到检查点$$$i$$$,跑步者可以从$$$m$$$可能的路径中选择一个。对于任何 $$$1\le j\le m$$$ 和 $$$1\le i\le n$$$,检查点 $$$i-1$$$ 和 $$$i$$$ 之间的第 $$$j$$$ 路径的长度为 $$$b_{i,j}$$$。
为了测试路线,我们有 $$$m$$$ 跑步者。每个跑步者必须从检查点 $$$0$$$ 跑到检查点 $$$n$$$ 一次,访问所有检查点。每对相邻检查点之间的每条路径都需要由一名跑步者跑完。如果跑步者选择检查点 $$$i-1$$$ 和 $$$i$$$ 之间长度为 $$$l_i$$$ 的路径 ($$$1\le i\le n$$$),则他的疲劳程度为 $$$$$$\min_{i=1}^n l_i,$$$$$$ i。 e.他所走路径的最小长度。
请合理安排$$$m$$$跑者的路径,以尽量减少他们的疲劳总和。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n,m \leq 100$$$)。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$b_{i,1}$$$、$$$b_{i,2}$$$、...、$$$b_{i,m}$$$ ($$$1 \le b_{i,j} \le 10^9$$$)。
保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$10^4$$$。
输出
对于每个测试用例,输出 $$$n$$$ 行。第 $$$i$$$ 行中的第 $$$j$$$ 数字应包含跑步者 $$$j$$$ 选择从检查点 $$$i-1$$$ 跑到检查点 $$$i$$$ 的路径长度。第 $$$i$$$ 行中应该正好有 $$$m$$$ 整数,并且对于所有 $$$1\le i\le n$$$,这些整数应形成 $$$b_{i, 1}$$$, ..., $$$b_{i, m}$$$ 的排列。
如果有多个答案,请打印其中一个。
示例
输入 #1
2 2 3 2 3 4 1 3 5 3 2 2 3 4 1 3 5
输出 #1
2 3 4 5 3 1 2 3 4 1 3 5
注意
在第一种情况下,疲劳总和为 $$$\min(2,5) + \min(3,3) + \min(4,1) = 6$$$。
在第二种情况下,疲劳总和为 $$$\min(2,4,3) + \min(3,1,5) = 3$$$。