#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAXN = 410;
const int INF = 1000000000;

int n, bn;
int a[MAXN][MAXN], u[MAXN * MAXN], b[MAXN + MAXN], c[MAXN][MAXN], d[MAXN][MAXN];
int whereX[MAXN * MAXN], whereY[MAXN * MAXN];
int dp[MAXN][MAXN], pI[MAXN][MAXN], pJ[MAXN][MAXN];

void goDP (int x, int y) {
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) dp[i][j] = INF;
    dp[0][0] = 0;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) if (i + j < bn && dp[i][j] < INF) {
        int num = b[i+j+1];
        int I = whereX[num];
        int J = whereY[num];
        if (i < n && dp[i + 1][j] > dp[i][j] + (I - x) * (I - x) + (J - (i+1)) * (J - (i+1)) ) {
            dp[i+1][j] = dp[i][j] + (I - x) * (I - x) + (J - (i+1)) * (J - (i+1));
            pI[i+1][j] = i;
            pJ[i+1][j] = j;
        }
        if (j < n && dp[i][j + 1] > dp[i][j] + (I - y) * (I - y) + (J - (j + 1)) * (J - (j + 1))) {
            dp[i][j+1] = dp[i][j] + (I - y) * (I - y) + (J - (j + 1)) * (J - (j + 1));
            pI[i][j+1] = i;
            pJ[i][j+1] = j;
        }
    }
    
}

void doOptSwap (int x, int y) {
    bn = 0;
    for(int i = 1; i <= n; i++) b[++bn] = a[x][i];
    for(int i = 1; i <= n; i++) b[++bn] = a[y][i];
    sort(b + 1, b + bn + 1);
    goDP(x, y);
    int res1 = dp[n][n];
    int I = n, J = n;
    while (I+J > 0) {
        int num = b[I+J];
        if (pI[I][J] == I) {
            c[y][J] = num;
            --J;
        } else {
            c[x][I] = num;
            --I;
        }
    }
    reverse(b + 1, b + bn + 1);
    goDP(x, y);
    int res2 = dp[n][n];
    I = n, J = n;
    while (I+J > 0) {
        int num = b[I+J];
        if (pI[I][J] == I) {
            d[y][J] = num;
            --J;
        } else {
            d[x][I] = num;
            --I;
        }
    }
    if (res1 < res2) {
        for(int i = 1; i <= n; i++) {
            a[x][i] = c[x][i];
            a[y][i] = c[y][i];
        }
    } else {
        for(int i = 1; i <= n; i++) {
            a[x][i] = d[x][i];
            a[y][i] = d[y][i];
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[i][j];
            u[a[i][j]] = 1;
            whereX[a[i][j]] = i;
            whereY[a[i][j]] = j;
            assert(1 <= a[i][j] && a[i][j] <= n * n);
        }
    }
    for(int i = 1; i <= n * n; i++) assert(u[i]==1);
    for(int i = 1; i < n; i++) {
        doOptSwap(i, i+1);
    }
    for(int i = 1; i < n-1; i++) {
        doOptSwap(i, i+2);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < n; j++) cout << a[i][j] << " ";
        cout << a[i][n] << endl;
    }
    return 0;
}