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 emplace_back
#define INF 1e9
#define N 210
using namespace std;
struct Info{int nu,ne,qu;}a[N*N];
int m,n,x,y,s,t,num=1,b[N],cur[N],an[N][N],li[N],di[N];
vector<int> c[N][N];
void jb(int x,int y){
	a[++num].nu=y;a[num].ne=b[x];b[x]=num;a[num].qu=1;
	a[++num].nu=x;a[num].ne=b[y];b[y]=num;a[num].qu=0;
}
int dinic(int x,int sh){
	if (x==t) return sh;
	int n1=0,n2;
	for (int y=cur[x];y;y=a[y].ne){
		cur[x]=y;
		if (di[a[y].nu]==di[x]+1&&a[y].qu){
			n2=dinic(a[y].nu,min(a[y].qu,sh-n1));
			n1+=n2;a[y].qu-=n2;a[y^1].qu+=n2;
			if (n1==sh) return n1;
		}
	}
	return n1;
}
bool bfs(){
	for (int i=1;i<=t;i++)di[i]=INF;
	int l=1,r=1;li[l]=s;di[s]=0;
	while (l<=r){
		for (int y=b[li[l]];y;y=a[y].ne)
			if (a[y].qu&&di[a[y].nu]==INF){di[a[y].nu]=di[li[l]]+1;li[++r]=a[y].nu;}
		l++;
	}
	return (di[t]!=INF);
}
int main(){
	cin>>n>>m;
	s=n+n+1,t=n+n+2;
	for (int i=1;i<=n;i++){jb(s,i);jb(i+n,t);}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){cin>>x;c[i][(x-1)/m+1].pb(x);jb(i,n+(x-1)/m+1);}
	for (int j=1;j<=m;j++){
		while (bfs()){for (int i=1;i<=t;i++)cur[i]=b[i];dinic(s,INF);}
		for (int i=1;i<=n;i++){
			a[i*2].qu=1;a[i*2+1].qu=0;
			a[(i+n)*2].qu=1;a[(i+n)*2+1].qu=0;
		}
		for (int i=3;i<=num;i+=2){
			if (a[i].qu){
				a[i].qu=0;y=a[i^1].nu-n;
				an[a[i].nu][j]=c[a[i].nu][y][c[a[i].nu][y].size()-1];
				c[a[i].nu][y].pop_back();
			}
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<m;j++)cout<<an[i][j]<<' ';
		cout<<an[i][m]<<endl;
	}
	for (int i=1;i<=m;i++){
		vector<int> no;no.clear();
		for (int j=1;j<=n;j++)no.pb(an[j][i]);
		sort(no.begin(),no.end());
		for (int j=1;j<=n;j++)an[j][i]=no[j-1];
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<m;j++)cout<<an[i][j]<<' ';
		cout<<an[i][m]<<endl;
	}
	return 0;
}