Волонтеры 2050 организуют мероприятие «Беги! Догони восходящее солнце». Начав 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$$$ возможных. Длина $$$j$$$-го пути между пунктами $$$i-1$$$ и $$$i$$$ равняется $$$b_{i,j}$$$ для всех $$$1\le j\le m$$$ и $$$1\le i\le n$$$.
Чтобы протестировать маршрут, у нас есть $$$m$$$ бегунов. Каждый бегун должен пробежать от пункта $$$0$$$ до пункта $$$n$$$ один раз, посетив все промежуточные пункты. Каждый путь между каждой парой соседних контрольных пунктов должен быть использован ровно одним бегуном. Если бегун выберет путь длины $$$l_i$$$ между пунктами $$$i-1$$$ и $$$i$$$ ($$$1\le i\le n$$$), его усталость будет равна $$$$$$\min_{i=1}^n l_i,$$$$$$ то есть минимальной длине из путей, по которым он пробежал.
Выберите пути для $$$m$$$ бегунов так, чтобы их суммарная усталость была минимальна.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n,m \leq 100$$$).
В $$$i$$$-й из следующих $$$n$$$ строк даны $$$m$$$ целых чисел $$$b_{i,1}$$$, $$$b_{i,2}$$$, ..., $$$b_{i,m}$$$ ($$$1 \le b_{i,j} \le 10^9$$$).
Гарантируется, что сумма $$$n\cdot m$$$ по всем наборам входных данных не превышает $$$10^4$$$.
Для каждого набора входных данных выведите $$$n$$$ строк. $$$j$$$-е число в $$$i$$$-й строке должно равняться длине пути, который $$$j$$$-й бегун выберет между контрольными пунктами $$$i-1$$$ и $$$i$$$. В $$$i$$$-й строке должно быть ровно $$$m$$$ целых чисел и эти числа должны образовывать перестановку чисел $$$b_{i, 1}$$$, ..., $$$b_{i, m}$$$ для всех $$$1\le i\le n$$$.
Если существует несколько решений, выведите любое.
2 2 3 2 3 4 1 3 5 3 2 2 3 4 1 3 5
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$$$.
