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<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int S=201,T=202;
struct bian
{
	int nxt,to,f;
}bi[60060];
int n,m,head[210],num,cnt[110][110],dep[210],cur[210],a[110][110],b[110][110],c[110][110],p[110];
bool used[110][110];
vector<int>s[110][110];
inline void add(int from,int to,int f){bi[++num]=bian{head[from],to,f};head[from]=num;}
inline void ADD(int from,int to,int f){add(from,to,f),add(to,from,0);}
bool bfs()
{
	queue<int>q;
	memset(dep,0,sizeof(dep));
	memcpy(cur,head,sizeof(head));
	q.push(S);dep[S]=1;
	int x,y;
	while(!q.empty())
	{
		x=q.front();q.pop();
		for(int i=head[x];i;i=bi[i].nxt)
			if(bi[i].f)
			{
				y=bi[i].to;
				if(!dep[y])dep[y]=dep[x]+1,q.push(y);
			}
	}
	return dep[T]!=0;
}
int dfs(int v,int last)
{
	if(v==T)return last;
	int now=0;
	for(int &i=cur[v],u;i;i=bi[i].nxt)
	{
		u=bi[i].to;
		if(bi[i].f&&dep[u]==dep[v]+1)
		{
			int dmin=dfs(u,min(last,bi[i].f));
			bi[i].f-=dmin,bi[i^1].f+=dmin;
			last-=dmin,now+=dmin;
			if(!last)break;
		}
	}
	return now;
}
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]),s[i][(a[i][j]-1)/m+1].push_back(a[i][j]);
	for(int c=1;c<=m;++c)
	{
		memset(head,0,sizeof(head));num=1;
		for(int i=1;i<=n;++i)ADD(S,i,1),ADD(i+n,T,1);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				if(s[i][j].size())ADD(i,j+n,1);
		while(bfs())
			while(dfs(S,0x3f3f3f3f));
		int cnt=0;
		for(int i=1;i<=n;++i)
			for(int j=head[i];j;j=bi[j].nxt)
				if(bi[j].to<=2*n&&!bi[j].f)
					b[i][c]=s[i][bi[j].to-n].back(),s[i][bi[j].to-n].pop_back();
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)printf("%d ",b[i][j]);
		printf("\n");
	}
	for(int j=1;j<=m;++j)
	{
		for(int i=1;i<=n;++i)p[i]=b[i][j];
		sort(p+1,p+1+n);
		for(int i=1;i<=n;++i)c[i][j]=p[i];
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)printf("%d ",c[i][j]);
		printf("\n");
	}
	return 0;
}