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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
int n,m,i,j,k,l,x,a[105][105],b[105][105],c[105][105],head[N],adj[N],nxt[N],flow[N],cap[N],cur[N],d[N],q[N],bg,ed;
bool v[105][105];
void addedge(int u,int v,int w)
{
	adj[++l]=v;
	nxt[l]=head[u];
	head[u]=l;
	flow[l]=0;
	cap[l]=w;
	adj[++l]=u;
	nxt[l]=head[v];
	head[v]=l;
	flow[l]=0;
	cap[l]=0;
}
bool bfs()
{
	int i;
	for(i=1;i<=2*n+2;++i)
		d[i]=1<<30;
	d[2*n+1]=0;
	q[bg=ed=1]=2*n+1;
	while(bg<=ed)
	{
		for(i=head[q[bg]];i;i=nxt[i])
			if(flow[i]<cap[i]&&d[adj[i]]==(1<<30))
			{
				d[adj[i]]=d[q[bg]]+1;
				q[++ed]=adj[i];
			}
		++bg;
	}
	return d[2*n+2]<(1<<30);
}
int dfs(int x,int a)
{
	if(x==2*n+2||a<=0)
		return a;
	int g,h=0;
	for(;cur[x];cur[x]=nxt[cur[x]])
		if(d[adj[cur[x]]]==d[x]+1&&(g=dfs(adj[cur[x]],min(cap[cur[x]]-flow[cur[x]],a)))>0)
		{
			flow[cur[x]]+=g;
			flow[cur[x]&1?cur[x]+1:cur[x]-1]-=g;
			a-=g;
			h+=g;
			if(a<=0)
				break;
		}
	return h;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",a[i]+j);
	for(i=1;i<=m;++i)
	{
		for(j=1;j<=2*n+2;++j)
			head[j]=0;
		l=0;
		for(j=1;j<=n;++j)
		{
			addedge(2*n+1,j,1);
			addedge(n+j,2*n+2,1);
		}
		for(j=1;j<=n;++j)
			for(k=1;k<=m;++k)
				if(!v[j][k])
					addedge(j,n+(a[j][k]-1)/m+1,1);
		while(bfs())
		{
			for(j=1;j<=2*n+2;++j)
				cur[j]=head[j];
			dfs(2*n+1,1<<30);
		}
		for(j=1;j<=n;++j)
		{
			for(k=head[j];k;k=nxt[k])
				if(adj[k]!=2*n+1&&flow[k]==1)
				{
					k=adj[k]-n;
					break;
				}
			for(x=1;x<=m;++x)
				if(!v[j][x]&&(a[j][x]-1)/m+1==k)
				{
					v[j][x]=true;
					b[j][i]=a[j][x];
					break;
				}
		}
	}
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			c[(b[i][j]-1)/m+1][j]=b[i][j];
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j)
			printf("%d ",b[i][j]);
		puts("");
	}
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j)
			printf("%d ",c[i][j]);
		puts("");
	}
	return 0;
}