← 返回题目列表

Codeforces · 2111/D

D. 创建时间表

中文机器翻译题面 查看原题

新学期即将开始,需要制定第一天的日程安排。学院共有 $$$n$$$ 个小组和 $$$m$$$ 个教室。还已知每个组在第一天正好有 $$$6$$$ 课,并且每个组的第 $$$k$$$ 课同时进行。每节课必须在一个教室进行,同时同一教室不能有超过一组的课程。

每个教室都有自己的索引(至少三位),该索引的所有数字(最后两位除外)表示该教室所在的楼层。例如,教室$$$479$$$位于$$$4$$$楼,而教室$$$31415$$$位于$$$314$$$楼。楼层之间可以通过楼梯移动;对于任何楼层 $$$x \gt 1$$$,可以下到楼层 $$$x - 1$$$ 或上到楼层 $$$x + 1$$$;从一楼只能上二楼;从$$$10^7$$$楼层(最后一层)开始,只能到达$$$9999999$$$楼层。

教务长办公室决定制定时间表,让学生尽可能在楼层之间移动,这意味着 所有组的楼层之间的移动总数应最大化。当学生从一层移动到另一层时,他们会走最短的路径。

例如,如果有$$$n = 2$$$个小组和$$$m = 4$$$教室$$$[479, 290, 478, 293]$$$,则时间表可以安排如下:

班级编号第 1 组第 2 组
$$$1$$$$$$290$$$$$$293$$$
$$$2$$$$$$478$$$$$$479$$$
$$$3$$$$$$293$$$$$$290$$$
$$$4$$$$$$479$$$$$$478$$$
$$$5$$$$$$293$$$$$$290$$$
$$$6$$$$$$479$$$$$$478$$$

在这样的时间表中,各组每次将在 $$$2$$$nd 和 $$$4$$$th 楼层之间移动,导致楼层之间总共 $$$20$$$ 移动。

帮助院长办公室制定任何合适的时间表!

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 10^{5}$$$) — 小组数量和可用教室数量。

每个测试用例的第二行包含 $$$m$$$ 整数 $$$a_{i}$$$ ($$$100 \le a_{i} \lt 10^{9}$$$) — 可用教室的索引。

输入的附加限制:

  • 所有教室的编号两两不同;
  • 所有测试用例的 $$$m$$$ 总和不超过 $$$10^{5}$$$。

输出

对于每个测试用例,输出 $$$n$$$ 行,其中第 $$$i$$$ 行应包含 $$$6$$$ 整数 - 将举办第 $$$i$$$ 组课程的教室的索引。

在第 $$$k$$$ 课期间,每个教室最多只能有一组人。

示例

输入
复制

3
2 4
479 290 478 293
1 1
31415
6 10
479 385 290 293 384 383 297 478 291 382

输出
复制

290 478 293 479 293 479
293 479 290 478 290 478
31415 31415 31415 31415 31415 31415
479 290 479 290 479 290
290 479 290 479 290 479
293 478 293 478 293 478
297 385 297 385 297 385
478 293 478 293 478 293
291 384 291 384 291 384

注意

在第三个测试用例中,教室之间的最大移动次数为 $$$50$$$。