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<queue>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
#define N 206
int head[N],cnt=1,dis[N],n,m,v[N][N],as[N][N],as2[N][N],cur[N];
multiset<int> sb[N],vl[N][N];
struct edge{int t,next,v;}ed[N*N*3];
void adde(int f,int t,int v){ed[++cnt]=(edge){t,head[f],v};head[f]=cnt;ed[++cnt]=(edge){f,head[t],0};head[t]=cnt;}
bool bfs(int s,int t)
{
	queue<int> v;
	memset(dis,-1,sizeof(dis));
	memcpy(cur,head,sizeof(cur));
	v.push(s);dis[s]=1;
	while(!v.empty())
	{
		int r=v.front();v.pop();
		for(int i=head[r];i;i=ed[i].next)
		if(dis[ed[i].t]==-1&&ed[i].v)
		{dis[ed[i].t]=dis[r]+1,v.push(ed[i].t);if(ed[i].t==t)return 1;}
	}
	return 0;
}
int dfs(int u,int t,int f)
{
	if(!f||(u==t))return f;
	int as=0,tp;
	for(int &i=cur[u];i;i=ed[i].next)
	if(ed[i].v&&dis[ed[i].t]==dis[u]+1&&(tp=dfs(ed[i].t,t,min(ed[i].v,f))))
	{
		ed[i].v-=tp,ed[i^1].v+=tp,as+=tp,f-=tp;
		if(!f)return as;
	}
	return as;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		scanf("%d",&v[i][j]);
		int v1=(v[i][j]-1)/m+1;
		sb[i].insert(v1),vl[i][v1].insert(v[i][j]);
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n*2+2;j++)head[j]=0;
		cnt=1;
		for(int j=1;j<=n;j++)
		{
			adde(n*2+1,j,1);adde(j+n,n*2+2,1);
			for(int k=1;k<=n;k++)
			{
				multiset<int>::iterator it=sb[j].lower_bound(k);
				if(it==sb[j].end()||*it!=k)continue;
				adde(j,k+n,1);
			}
		}
		while(bfs(n*2+1,n*2+2))dfs(n*2+1,n*2+2,1e8);
		for(int j=1;j<=n;j++)
		for(int k=head[j];k;k=ed[k].next)
		if(!ed[k].v)
		{
			int l=j,r=ed[k].t-n;
			as[l][i]=as2[i][l]=*vl[l][r].begin();
			vl[l][r].erase(vl[l][r].begin());
			sb[l].erase(sb[l].find(r));
		}
	}
	for(int i=1;i<=n;i++,printf("\n"))
	for(int j=1;j<=m;j++)
	printf("%d ",as[i][j]);
	for(int i=1;i<=m;i++)sort(as2[i]+1,as2[i]+n+1);
	for(int i=1;i<=n;i++,printf("\n"))
	for(int j=1;j<=m;j++)
	printf("%d ",as2[j][i]);
}