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>
#define pb push_back
#define ll long long
#define ii pair<int,int>
#define st first
#define nd second
#define N 205
#define inf 1000000000
#define MOD 998244353
#define sz(x) ((int)x.size())
#define umax(x,y) x=max(x,y)
using namespace std;

int n,m,tot,etot;
int sink,source;
int a[N][N],node[N],idn[N],vis[3*N];
vector<int> v[3*N];

struct edge {

	int go,cap;

} e[N*N];

int id(int val) {

	return (val+m-1)/m;

}

void print() {

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=m;j++) {

			printf("%d ",a[i][j]);

		}

		printf("\n");

	}

}

void solve_p_col(int c) {

	vector<int> vals;

	for(int i=1;i<=n;i++) vals.pb(a[i][c]);

	sort(vals.begin(),vals.end());

	for(int i=0;i<n;i++) a[i+1][c]=vals[i];	

}

void solve_cols() {

	for(int i=1;i<=m;i++) {

		solve_p_col(i);

	}

	print();

}

void bring(int row,int col,int idd) {

	for(int j=col;j<=m;j++) {

		if(id(a[row][j])==idd) {

			swap(a[row][col],a[row][j]);

			return ;

		}

	}

	assert(0);

}

int dfs(int node) {

	if(node==sink) return 1;

	vis[node]=1;

	for(int i:v[node]) {

		if(!vis[e[i].go] && e[i].cap && dfs(e[i].go)) {

			e[i].cap=0;
			e[i^1].cap=1;

			return 1;

		}

	}

	return 0;

}

void add_edge(int x,int y) {

	v[x].pb(etot);
	e[etot++]={y,1};
	v[y].pb(etot);
	e[etot++]={x,0};

}

void clear_network() {

	for(int i=1;i<=tot;i++) {

		v[i].clear();

	}

	etot=tot=0;

}

int nn() {return ++tot;}

void solve_col(int c) {

	clear_network();

	source=nn();
	sink=nn();

	for(int i=1;i<=n;i++) node[i]=nn(),add_edge(source,node[i]);
	for(int i=1;i<=n;i++) idn[i]=nn(),add_edge(idn[i],sink);

	for(int i=1;i<=n;i++) {

		for(int j=c;j<=m;j++) {

			add_edge(node[i],idn[id(a[i][j])]);

		}

	}

	do {

		fill(vis+1,vis+tot+1,0);

	} while(dfs(source));

	for(int i=1;i<=n;i++) {

		for(int ednum:v[node[i]]) {

			if(e[ednum].cap==0 && e[ednum].go>=idn[1] && e[ednum].go<=idn[n]) {

				bring(i,c,e[ednum].go-idn[1]+1);

				break ;

			}

		}

	}

}

void solve_rows() {

	for(int i=1;i<=m;i++) {

		solve_col(i);

	}

	print();

}

int main(int arg,char* argv[]) {

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=m;j++) {

			scanf("%d",&a[i][j]);

		}

	}

	solve_rows();
	solve_cols();

}