#include <stdio.h>
#include <stdlib.h>

int main() {
    // вводим размер матрицы
    int n;
    scanf("%d", &n);
    // выделяем память под "массив массивов"
    int **M = (int **)malloc(sizeof(int *) * n);

    for (int i = 0; i < n; i++) {
        // выделяем память под каждый массив в "массиве массивов"
        M[i] = (int *)malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++) {
            // читаем элементы матрицы
            scanf("%d", &M[i][j]);
        }
    }

    // проводим сортировку выбором для каждой диагонали
    for (int diag = 1; diag < n - 1; diag++) {
        for (int i = 0; i < n - diag; i++) {
            int max_pos = i;
            for (int j = i + 1; j < n - diag; j++) {
                if (M[max_pos][max_pos + diag] < M[j][j + diag]) {
                    max_pos = j;
                }
            }

            if (max_pos != i) {
                int t = M[i][i + diag];
                M[i][i + diag] = M[max_pos][max_pos + diag];
                M[max_pos][max_pos + diag] = t;
            }
        }
    }

    // выводим матрицу
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", M[i][j]);
        }
        printf("\n");
    }

    return 0;
}