E. Обмен крестом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана квадратная матрица $$$A$$$ размера $$$n \times n$$$, элементы которой — целые числа. Обозначим элемент на пересечении $$$i$$$-й строки и $$$j$$$-го столбца за $$$A_{i,j}$$$.

Вы можете выполнять некоторые операции над матрицей. На каждой операции вы выбираете индекс $$$k$$$, а затем для всех $$$i$$$ ($$$1 \leq i \leq n$$$) меняете местами $$$A_{i, k}$$$ и $$$A_{k, i}$$$. Обратите внимание, что элемент $$$A_{k, k}$$$ не меняется.

Например, для $$$n = 4$$$ и $$$k = 3$$$ матрица будет преобразована следующим образом:

Операция $$$k = 3$$$ меняет местами синюю строку и зеленый столбец.

Вы можете выполнять эту операцию произвольное количество раз. Найдите лексикографически минимальную матрицу$$$^\dagger$$$, которую вы можете получить после выполнения произвольного числа операций.

$$${}^\dagger$$$ Для двух матриц $$$A$$$ и $$$B$$$ размера $$$n \times n$$$ положим $$$a_{(i-1) \cdot n + j} = A_{i,j}$$$ и $$$b_{(i-1) \cdot n + j} = B_{i,j}$$$. Тогда матрица $$$A$$$ лексикографически меньше матрицы $$$B$$$, если существует индекс $$$i$$$ ($$$1 \leq i \leq n^2$$$) такой, что $$$a_i < b_i$$$ и для всех индексов $$$j$$$ таких, что $$$1 \leq j < i$$$, выполняется $$$a_j = b_j$$$.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$) — размер матрицы.

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$n$$$ целых чисел $$$A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$$$ ($$$1 \le A_{i, j} \le 10^9$$$) — описание матрицы $$$A$$$.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ строк по $$$n$$$ чисел — лексикографически минимальную матрицу.

Пример
Входные данные
2
3
2 1 2
2 1 2
1 1 2
4
3 3 1 2
1 1 3 1
3 2 3 2
2 3 3 1
Выходные данные
2 1 1
2 1 1
2 2 2
3 1 1 2
3 1 2 1
3 3 3 3
2 3 2 1
Примечание

На каждом рисунке ниже преобразование матрицы меняет местами синюю строку и зеленый столбец.

В первом наборе входных данных можно выполнить $$$1$$$ операцию с $$$k = 3$$$. Матрица будет преобразована следующим образом:

Во втором наборе можно выполнить $$$2$$$ операции с $$$k = 1$$$ и $$$k = 3$$$: