D. Составляем расписание
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скоро начинается новый семестр, и необходимо составить расписание на первый день. Всего на факультете есть $$$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$$$ и $$$4$$$ этажом, и суммарно будет $$$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$$$.