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;
const int maxn=2E4+5;
int n,m,a[105][105],b[105][105],c[105][105];
namespace flow
{
	int size,head[maxn];
	int S,T,dfn[maxn];
	struct edge
	{
		int to,next,w,id;
	}E[maxn*2];
	inline void addE(int u,int v,int w,int id)
	{
		E[++size].to=v;
		E[size].next=head[u];
		E[size].w=w;
		E[size].id=id;
		head[u]=size;
	}
	inline void add(int u,int v,int w,int id)
	{
		addE(u,v,w,id);
		addE(v,u,0,id);
	}
	inline void clear()
	{
		memset(head,0,sizeof(head));
		memset(E,0,sizeof(E));
		size=1;
	}
	inline bool bfs()
	{
		for(int i=0;i<=T;++i)
			dfn[i]=-1;
		queue<int>Q;
		Q.push(S);
		dfn[S]=0;
		while(!Q.empty())
		{
			int u=Q.front();
			Q.pop();
			for(int i=head[u];i;i=E[i].next)
			{
				int v=E[i].to;
				if(E[i].w==0||dfn[v]!=-1)
					continue;
				dfn[v]=dfn[u]+1;
				Q.push(v);
			}
		}
		return dfn[T]!=-1;
	}
	int dfs(int u,int up)
	{
		if(u==T)
			return up;
		int s=0;
		for(int i=head[u];i;i=E[i].next)
		{
			int v=E[i].to;
			if(dfn[v]!=dfn[u]+1||E[i].w==0)
				continue;
			int g=dfs(v,min(E[i].w,up-s));
			E[i].w-=g;
			E[i^1].w+=g;
			s+=g;
			if(g==0)
				dfn[v]=-1;
			if(s==up)
				break;
		}
		return s;
	}
	inline void solve()
	{
		int s=0;
		while(bfs())
			s+=dfs(S,123456);
		assert(s==n);
	}
}
inline int get(int x)
{
	return (x-1)/m+1;
}
bool used[105*105];
inline void solve()
{
	for(int e=1;e<=m;++e)
	{
		flow::clear();
		flow::S=0;
		flow::T=2*n+1;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				if(!used[a[i][j]])
					flow::add(i,n+get(a[i][j]),1,a[i][j]);
		for(int i=1;i<=n;++i)
			flow::add(0,i,1,0),flow::add(i+n,2*n+1,1,0);
		flow::solve();
		using namespace flow;
		for(int u=1;u<=n;++u)
			for(int i=head[u];i;i=E[i].next)
				if(E[i].w==0)
				{
					used[E[i].id]=1;
					b[u][e]=E[i].id;
					c[get(E[i].id)][e]=E[i].id;
				}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			cin>>a[i][j];
	solve();
	for(int i=1;i<=n;++i,cout<<endl)
		for(int j=1;j<=m;++j)
			cout<<b[i][j]<<" ";
	for(int i=1;i<=n;++i,cout<<endl)
		for(int j=1;j<=m;++j)
			cout<<c[i][j]<<" ";
	return 0;
}