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 long long ll;
const int N=205,M=21005,inf=0x3f3f3f3f,INF=0x7fffffff;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,m,cnt,S,T,ans,a[N][N],b[N],col[N*N];
int fir[N],firr[N],siz;
struct edge{int u,v,w,nex;}e[M];
void add(int u,int v,int w){
	e[++siz]=(edge){u,v,w,fir[u]};fir[u]=siz;
	e[++siz]=(edge){v,u,0,fir[v]};fir[v]=siz;
}
int dist[N],que[N];
void dec(int x,int fl){e[x].w-=fl;e[x^1].w+=fl;}
bool bfs(int S,int T){
	memset(dist,0x3f,4*(cnt+1));
	int l=1,r=1;que[l]=S;dist[S]=0;
	while (l<=r){
		int x=que[l];
		for (int i=fir[x];i;i=e[i].nex)
		if ((e[i].w)&&(dist[e[i].v]>dist[x]+1)){
			que[++r]=e[i].v;
			dist[e[i].v]=dist[x]+1;
		}
		l++;
	}
	return dist[T]!=inf;
}
int dfs(int x,int flow,int &T){
	if (x==T) return flow;
	int fl=0,t=0;
	for (int i=firr[x];i;i=e[i].nex)
	if (e[i].w&&(dist[e[i].v]>dist[x])){
		t=dfs(e[i].v,min(flow-fl,e[i].w),T);
		dec(i,t);fl+=t;
		if (fl==flow) {firr[x]=i;return fl;}
	}
	firr[x]=0;
	return fl;
}
ll dinic(){
	ll flow=0;
	while (bfs(S,T)){
		for (int i=0;i<=cnt;i++) firr[i]=fir[i];
		flow+=dfs(S,2147483647,T);
		cerr<<flow<<endl;
	}
	return flow;
}
int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++) a[i][j]=read(),col[++cnt]=i;
	for (int k=1;k<=m;k++){
		S=0;T=cnt=n*2+1;
		siz=1;memset(fir,0,sizeof(fir));
		for (int i=1;i<=n;i++){
			add(S,i,1);
			add(i+n,T,1);
			for (int j=k;j<=m;j++)
			add(i,n+col[a[i][j]],1);
		}
		assert(dinic()==n);
		for (int i=2;i<siz;i+=2)
		if ((e[i].u<=n)&&(e[i].v>n)&&e[i^1].w) b[e[i].u]=e[i].v-n;
		for (int i=1;i<=n;i++)
		for (int j=k;j<=m;j++)
		if (col[a[i][j]]==b[i]) swap(a[i][j],a[i][k]);
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) printf("%d ",a[i][j]);
		printf("\n");
	}
	for (int j=1;j<=m;j++){
		for (int i=1;i<=n;i++) b[col[a[i][j]]]=a[i][j];
		for (int i=1;i<=n;i++) a[i][j]=b[i];
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) printf("%d ",a[i][j]);
		printf("\n");
	}
	return 0;
}