Problem: We have a grid with N rows and M columns of squares. Each integer from 1 to NM is written in this grid once. The number written in the square at the i-th row from the top and the j-th column from the left is A_{ij}.

You need to rearrange these numbers as follows:

1. First, for each of the N rows, rearrange the numbers written in it as you like.
2. Second, for each of the M columns, rearrange the numbers written in it as you like.
3. Finally, for each of the N rows, rearrange the numbers written in it as you like.



After rearranging the numbers, you want the number written in the square at the i-th row from the top and the j-th column from the left to be M\times (i-1)+j. Construct one such way to rearrange the numbers. The constraints guarantee that it is always possible to achieve the objective.

Constraints

* 1 \leq N,M \leq 100
* 1 \leq A_{ij} \leq NM
* A_{ij} are distinct.

Input

Input is given from Standard Input in the following format:


N M
A_{11} A_{12} ... A_{1M}
:
A_{N1} A_{N2} ... A_{NM}


Output

Print one way to rearrange the numbers in the following format:


B_{11} B_{12} ... B_{1M}
:
B_{N1} B_{N2} ... B_{NM}
C_{11} C_{12} ... C_{1M}
:
C_{N1} C_{N2} ... C_{NM}


Here B_{ij} is the number written in the square at the i-th row from the top and the j-th column from the left after Step 1, and C_{ij} is the number written in that square after Step 2.

Examples

Input

3 2
2 6
4 3
1 5


Output

2 6
4 3
5 1
2 1
4 3
5 6


Input

3 4
1 4 7 10
2 5 8 11
3 6 9 12


Output

1 4 7 10
5 8 11 2
9 12 3 6
1 4 3 2
5 8 7 6
9 12 11 10

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

//bipartite matching
const int MAX_V = 210;

int V; 
vector<int> g[MAX_V];
int match[MAX_V];
bool used[MAX_V];

void init() {
	rep(i, MAX_V) g[i].clear();
}

inline void add_edge(int u, int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}

bool dfs(int v) {
	used[v] = true;

	for (int u : g[v]) {
		int w = match[u];
		if (w < 0 || (!used[w] && dfs(w))) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}

	return false;
}

int bipartite_matching() {
	int res = 0;
	memset(match, -1, sizeof(match));

	for (int v = 0; v < V; ++v) {
		if (match[v] < 0) {
			memset(used, 0, sizeof(used));
			res += dfs(v);
		}
	}

	return res;
}

const int MX = 110;

bool us[MX * MX];
int A[MX][MX], B[MX][MX], C[MX][MX];

int main() {
	int N, M;
	cin >> N >> M;

	rep(i, N) rep(j, M) {
		cin >> A[i][j];
		--A[i][j];
	}

	V = N + N;

	rep(j, M) {
		init();
		rep(p, N) rep(q, M) {
			int x = A[p][q];
			if (!us[x]) {
				add_edge(p, x / M + N);
			}
		}
		int mt = bipartite_matching();

		rep(p, N) {
			int c = match[p] - N;
			int to = -1;
			rep(q, M) {
				int x = A[p][q];
				if (!us[x] && x / M == c) {
					to = x;
				}
			}
			B[p][j] = to;
			us[to] = 1;
		}
	}

	rep(j, M) {
		rep(i, N) {
			rep(p, N) if (B[p][j] / M == i) {
				C[i][j] = B[p][j];
			}
		}
	}

	rep(i, N) {
		rep(j, M) {
			printf("%d%c", B[i][j] + 1, j == M-1 ? '\n' : ' ');
		}
	}

	rep(i, N) {
		rep(j, M) {
			printf("%d%c", C[i][j] + 1, j == M-1 ? '\n' : ' ');
		}
	}

	return 0;
}