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;
namespace maxflow
{
	#define inf 999999999
	struct edge
	{
		int to,nxt,f;
	}e[200001];
	int head[211];
	int edge_cnt;
	int s,t;
	void init(int s1,int t1)
	{
		s=s1,t=t1;
		edge_cnt=-1;
		memset(head,-1,sizeof(head));
	}
	void add(int u,int v,int f)
	{
		e[++edge_cnt].nxt=head[u];
		e[edge_cnt].to=v;
		e[edge_cnt].f=f;
		head[u]=edge_cnt;
	}
	void add_edge(int u,int v,int f)
	{
		add(u,v,f);
		add(v,u,0);
	}
	int dep[211];
	bool bfs(int s,int t)
	{
		memset(dep,0x3f,sizeof(dep));
		queue<int>q;
		q.push(s);
		dep[s]=0;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			for(int i=head[u];i!=-1;i=e[i].nxt)
				if(e[i].f!=0)
				{
					int to=e[i].to;
					if(dep[to]>dep[u]+1)
					{
						dep[to]=dep[u]+1;
						q.push(to);
					}
				}
		}
		return dep[t]<inf;
	}
	int dfs(int u,int flow)
	{
		if(u==t) return flow;
		int use=flow;
		for(int i=head[u];i!=-1;i=e[i].nxt)
		{
			int to=e[i].to;
			if(use&&dep[to]==dep[u]+1&&e[i].f)
			{
				int f=dfs(to,min(e[i].f,use));
				use-=f;
				e[i].f-=f;
				e[i^1].f+=f;
			}
		}
		return flow-use;
	}
	int dinic()
	{
		int maxflow=0;
		while(bfs(s,t))
			maxflow+=dfs(s,inf);
		return maxflow;
	}
}
using namespace maxflow;
int c[101][101];
int a[101][101];
vector<int>rem[101][101];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			rem[i][(a[i][j]+m-1)/m].push_back(a[i][j]);
		}
	for(int p=1;p<=m;p++)
	{
		init(0,210);

		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				if(rem[i][j].size())
					add_edge(i,j+n+1,1);
			add_edge(s,i,1);
			add_edge(i+n+1,t,1);
		}
		dinic();
	//	printf("%d\n",dinic());
		for(int i=1;i<=n;i++)
		{
			int at=0;
			for(int j=head[i];j!=-1;j=e[j].nxt)
				if(e[j].f==0&&e[j].to>n+1)
					at=e[j].to-n-1;
			c[i][p]=rem[i][at].back();
			rem[i][at].pop_back();
		}
	//	for(int t=1;t<=n;t++)
	//		printf("%d ",c[t][p]);
	//	printf("\n");
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",c[i][j]);
		printf("\n");
	}
	for(int j=1;j<=m;j++)
	{
		for(int i=1;i<=n;i++)
			for(int k=i+1;k<=n;k++)
				if(c[k][j]<=c[i][j])
					swap(c[k][j],c[i][j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",c[i][j]);
		printf("\n");
	}
	return 0;
}