Вам дана квадратная матрица \(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\).
Примечание
На каждом рисунке ниже преобразование матрицы меняет местами синюю строку и зеленый столбец.
В первом наборе входных данных можно выполнить \(1\) операцию с \(k = 3\). Матрица будет преобразована следующим образом:
Во втором наборе можно выполнить \(2\) операции с \(k = 1\) и \(k = 3\):
