Волонтеры 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\) бегунов так, чтобы их суммарная усталость была минимальна.
Выходные данные
Для каждого набора входных данных выведите \(n\) строк. \(j\)-е число в \(i\)-й строке должно равняться длине пути, который \(j\)-й бегун выберет между контрольными пунктами \(i-1\) и \(i\). В \(i\)-й строке должно быть ровно \(m\) целых чисел и эти числа должны образовывать перестановку чисел \(b_{i, 1}\), ..., \(b_{i, m}\) для всех \(1\le i\le n\).
Если существует несколько решений, выведите любое.
Примечание
В первом наборе входных данных сумма усталостей равна \(\min(2,5) + \min(3,3) + \min(4,1) = 6\).
Во втором наборе входных данных сумма усталостей равна \(\min(2,4,3) + \min(3,1,5) = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|