#include <bits/stdc++.h>
using namespace std;
vector<array<long long, 3>> euler(vector<vector<array<long long, 2>>> &adj) {
// funzione autoesplicativa, restituisce la lista di archi direzionati
// con in ingresso la lista di adiecenza dei non direzionati
long long n = adj.size(), aus = -1;
queue<long long> st; // starting points dispari
vector<bool> vis(n, 0); // controllo i nodi visitati (per componente conessa)
vector<long long> ind(n, 0); //tengo gli indici per non riscorrere tutti gli archi nella dfs
unordered_set<long long> used; //tengo gli archi usati per direzionare only once
vector<array<long long, 3>> ris; //da restituire!!
for (long long i = 0; i < n; i++) {
if (adj[i].size() %2) st.push(i); // se il nodo ha numero di archi dispari deve essere un inizio o una fine
}
function<void(long long, long long)> dfs = [&](long long a, long long s) {
if (!vis[a] && adj[a].size()%2) {
adj[s].push_back({a, aus});
adj[a].push_back({s, aus--});
}
vis[a] = 1; // visitato
for (long long &t = ind[a]; t < adj[a].size();) {
t++; // aumento il puntatore e non riconsidero l'arco
// se ripasso nel nodo
if (used.count(adj[a][t-1][1])) continue;
used.insert(adj[a][t-1][1]); // l'arco e' stato direzionato
ris.push_back({a, adj[a][t-1][0], adj[a][t-1][1]});
dfs(adj[a][t-1][0], s); //continuo la dfs
}
};
// itero su tutti gli inizi non gia' visitati
while (!st.empty()) {
if (!vis[st.front()]) dfs(st.front(), st.front());
st.pop();
}
// itero su tutti gli altri nodi (componenti dove posso iniziare il tour dove voglio)
for (long long i = 0; i < n; i++) {
if (vis[i]) continue;
dfs(i, -1);
}
return ris;
}
int main() {
//ingresso di variabili e matrice
long long N, S, T; cin >> N >> S >> T;
vector<vector<long long>> mat(N, vector<long long> (S));
for (long long i = 0; i < N; i++) {
for (long long j = 0; j < S; j++) cin >> mat[i][j];
}
// funzione ricorsiva top-down per ordinare i segmenti successivamente
function<void(long long, long long)> order = [&](long long l, long long r /* [) */) {
if (l == r-1) return; // sono arrivata all'intervallo 1
long long mid = (l+r)/2;
//INDEX COMPRESSION
vector<long long> f;
for (long long i = 0; i < N; i++) {
for (long long a = l; a < r; a++) f.push_back(mat[i][a]);
}
sort(f.begin(), f.end()); f.erase(unique(f.begin(), f.end()), f.end());
unordered_map<long long, long long> comp;
for (long long i = 0; i < f.size(); i++) comp.insert({f[i], i});
// ora ho un numero lineare di nodi invece che sempre T
// creo la lista di adiacenza, con unique identifiers per
// i multi-edges e ricordando in che riga era questo edge
// gli archi sono fra parte sinistra e destra della riga centrale
// a coppie ordinate
vector<vector<array<long long, 2>>> adj(f.size());
for (long long i = 0; i < N; i++) {
for (long long a = l; a < mid; a++) {
adj[comp[mat[i][a]]].push_back({comp[mat[i][a+mid-l]], i*S+a});
adj[comp[mat[i][a+mid-l]]].push_back({comp[mat[i][a]], i*S+a});
}
}
// prendo il risultato e lo rimetto nella matrice
// tutti i primi vanno messi nella prima meta'
// gli altri nella seconda
vector<array<long long, 3>> ris = euler(adj);
vector<long long> num(N, 0);
for (auto x : ris) {
if (x[2] < 0) continue;
x[2]/= S;
mat[x[2]][l+num[x[2]]] = f[x[0]];
mat[x[2]][mid+num[x[2]]] = f[x[1]];
num[x[2]]++;
}
// ricorro nei due segmenti sottostanti
order(l, mid);
order(mid, r);
};
order(0, S);
cout << endl;
for (long long i = 0; i < N; i++) {
for (long long j = 0; j < S; j++) cout << mat[i][j] << " ";
cout << "\n";
}
}
