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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct Edge{
	int v,c,nxt;
}e[50010];int tot;
int first[210];
void build(int u,int v,int c)
{
	e[++tot]=(Edge){v,c,first[u]};
	first[u]=tot;
	return ;
}
void adde(int u,int v,int c)
{
	build(u,v,c);
	build(v,u,0);
	return ;
}
int S,T;
int dep[210];
queue<int>q;
bool bfs()
{
	memset(dep,0,sizeof(dep));
	dep[S]=1;q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=first[u];i;i=e[i].nxt)
			if(e[i].c&&!dep[e[i].v])
			{
				dep[e[i].v]=dep[u]+1;
				q.push(e[i].v);
			}
	}
	return dep[T]>0;
}
int cur[210];
int dfs(int u,int flow)
{
	if(u==T)return flow;
	for(int &i=cur[u];i;i=e[i].nxt)
		if(e[i].c&&dep[u]+1==dep[e[i].v])
		{
			int d=dfs(e[i].v,min(flow,e[i].c));
			if(d){
				e[i].c-=d;
				e[i^1].c+=d;
				return d;
			}
		}
	return 0;
}
void dinic()
{
	int ans=0;
	while(bfs())
	{
		for(int i=0;i<=T;i++)
			cur[i]=first[i];
		int d;
		while(d=dfs(S,1e9))ans+=d;
	}
//	printf("%d\n",ans);
	return ;
}
int n,m;
int a[110][110];
int b[110][110];
int c[110][110];
bool book[110][110];
int col(int x)
{
	return (x-1)/m+1;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=m;i++)
	{
		tot=1;memset(first,0,sizeof(first));
		S=0;T=2*n+1;
		for(int j=1;j<=n;j++)
		{
			adde(S,j,1);
			adde(j+n,T,1);
		}
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
				if(!book[j][k])
					adde(j,n+col(a[j][k]),1);
		dinic();
		for(int j=1;j<=n;j++)
		{
			int ccol=0;
			for(int k=first[j];k;k=e[k].nxt)
			{
				int v=e[k].v-n;
				if(e[k].c||v<1||v>n)continue;
				ccol=v;break;
			}
			for(int k=1;k<=m;k++)
				if(!book[j][k]&&col(a[j][k])==ccol){
					book[j][k]=true;
					b[j][i]=a[j][k];
					break;
				}
		}
	}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				if(col(b[k][i])==j)c[j][i]=b[k][i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			printf("%d%c",b[i][j],j==m?'\n':' ');
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			printf("%d%c",c[i][j],j==m?'\n':' ');
	return 0;
}