#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;

const double eps = 1e-9;
const int oo = 0x3f3f3f3f;
const int mod = 1000000007;

struct graph
{
	int L, R;
	vector<vector<int>> adj;
    vector<int> mate;

	graph(int L, int R) : L(L), R(R), adj(L + R) {}

	void add_edge(int u, int v)
	{
        // cerr << "add edge: " << u << " " << v << endl;
		adj[u].push_back(v + L);
		adj[v + L].push_back(u);
	}

	int maximum_matching()
	{
		vector<int> visited(L);
        mate = vector<int>(L + R, -1);

		function<bool(int)> augment = [&](int u)
		{
			if (visited[u]) return false;
			visited[u] = true;
			for (int w : adj[u])
			{
				int v = mate[w];
				if (v < 0 || augment(v))
				{
					mate[u] = w;
					mate[w] = u;
					return true;
				}
			}
			return false;
		};
		int match = 0;
		for (int u = 0; u < L; ++u)
		{
			fill(visited.begin(), visited.end(), 0);
			if (augment(u))
				++match;
		}
		return match;
	}
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> b0(n, vi(m));
    vector<vector<int>> pi(n, vi(m));

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            cin >> b0[i][j];
            pi[i][j] = (b0[i][j] - 1) / m;
            // cerr << pi[i][j] << " ";
        }
        // cerr << endl;
    }

    vector<vector<int>> seen(n, vi(n, -1));
    vector<vector<int>> where(n, vi(n, -1));

    for (int col = 0; col < m; ++col){
        // cerr << "\n COL: " << col << endl << endl;
        graph g(n, n);

        for (int i = 0; i < n; ++i){
            for (int j = col; j < m; ++j){
                int u = pi[i][j];

                // cerr << "H: " << i << " " << j << " " << u << " " << seen[i][u] << endl;

                if (seen[i][u] != col){
                    // cerr << "V" << endl;
                    seen[i][u] = col;
                    where[i][u] = j;
                    g.add_edge(i, u);
                }

                // for (auto row : seen)
                //     for (auto vv : row) cerr << vv << " ";
                // cerr << endl;
            }
        }

        assert(g.maximum_matching() == n);

        for (int i = 0; i < n; ++i){
            int u = g.mate[i] - n;
            int j = where[i][u];

            // cout << i << " " << u << " " << j << endl;

            swap(b0[i][col], b0[i][j]);
            swap(pi[i][col], pi[i][j]);
        }

        // for (int i = 0; i < n; ++i){
        //     for (int j = 0; j < m; ++j){
        //         cout << b0[i][j] << " ";
        //     }
        //     cout << endl;
        // }
    }

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            cout << b0[i][j] << " ";
        }
        cout << endl;
    }

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            while (true) {
                int row = (b0[i][j] - 1) / m;
                if (row == i) break;
                swap(b0[i][j], b0[row][j]);
            }
        }
    }

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            cout << b0[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 640