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;
#define f(a,b,c) for(int a=(b);a<=(c);++a)
const int maxn=3e4+2;
int he[maxn],ne[maxn],to[maxn],w[maxn],cnt=1;
inline void addedge(int x,int y,int z)
{
	ne[++cnt]=he[x],he[x]=cnt,to[cnt]=y,w[cnt]=z;
	ne[++cnt]=he[y],he[y]=cnt,to[cnt]=x,w[cnt]=0;
}
int S,T;
int dis[maxn],inq[maxn];
int bfs()
{
	f(i,1,T)inq[i]=dis[i]=0;
	queue<int>q;q.push(S),dis[S]=1;
	while(q.size())
	{
		int x=q.front();q.pop();inq[x]=0;
		for(int i=he[x];i;i=ne[i])
		{
			if(w[i]&&!dis[to[i]])
			{
				dis[to[i]]=dis[x]+1;
				if(!inq[to[i]])
				{
					inq[to[i]]=1;
					q.push(to[i]);
				}
			 } 
		}
	}
	return dis[T];
}
int cur[maxn];
int dfs(int x,int f)
{
	if(f==0||x==T)return f;
	int ans=0;
	for(int i=cur[x];i&&ans<f;i=ne[i])
	{
		cur[x]=i;
		if(dis[x]+1==dis[to[i]]&&w[i]){
			int qwq=dfs(to[i],min(f-ans,w[i]));
			ans+=qwq;w[i]-=qwq;w[i^1]+=qwq;
		}
	}
	return ans;
}
int dinic()
{
	int ans=0;
	while(bfs())
	{
		f(i,1,T)cur[i]=he[i];
		ans+=dfs(S,1e9);
	}
	return ans;
}
vector<int>c[101][101];
int n,m;
int a[101][101];
int e[101][101];
int b[101][101];
void clear()
{
	cnt=1;
	f(i,1,T)he[i]=0;
}
int qwq[101];
int main()
{
	scanf("%d%d",&n,&m);
	f(i,1,n)f(j,1,m)scanf("%d",&a[i][j]),c[i][(a[i][j]-1)/m+1].push_back(a[i][j]);
	S=n+n+1,T=S+1;
    f(k,1,m)
    {
//    	cout<<k<<":\n";
    	f(i,1,n)f(j,1,n)
    	{
    		e[i][j]=-1;
    		if(c[i][j].size())
    		{
    			addedge(i,n+j,1);
    			e[i][j]=cnt-1;
//    			cout<<i<<" "<<j<<"\n";
			}
		}
		f(i,1,n)
		{
		    addedge(S,i,1);
		    addedge(i+n,T,1);
		}
		dinic();
		f(i,1,n)f(j,1,n)
		{
			if(e[i][j]>=0&&w[e[i][j]]==0)
			{
				b[i][k]=c[i][j][c[i][j].size()-1];
				c[i][j].pop_back();
				break;
			}
		}
		clear();
	}
	f(i,1,n)f(j,1,m)printf("%d%c",b[i][j]," \n"[j==m]);
	f(j,1,m)
	{
		f(i,1,n)qwq[i]=b[i][j];
		sort(qwq+1,qwq+n+1);
		f(i,1,n)b[i][j]=qwq[i];
	}
	f(i,1,n)f(j,1,m)printf("%d%c",b[i][j]," \n"[j==m]);
	return 0;
	
}