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=105;
int n,m,a[Maxn][Maxn],b[Maxn][Maxn],c[Maxn][Maxn];
queue<int>son[Maxn][Maxn];
namespace dinic{
	const int Maxn=2*::Maxn,Maxm=::Maxn*::Maxn+2*::Maxn;
	struct node{int to,next,v,pair;}e[2*Maxm];
	int cnt,S,T,h[Maxn],bl[Maxn],dis[Maxn],cur[Maxn];
	void AddEdge(int x,int y,int v,int pair){
		e[cnt]=(node){y,h[x],v,pair};h[x]=cnt;
	}
	void AddEdge(int x,int y,int v){
		AddEdge(x,y,v,++cnt+1);
		AddEdge(y,x,0,++cnt-1);
	}
	void reset(){
		memset(h,cnt=0,sizeof(h));
	}
	bool bfs(){
		memset(dis,0x3f,sizeof(dis));
		dis[S]=0;
		queue<int>Q;Q.push(S);
		while(Q.size()){
			int x=Q.front();Q.pop();
			for(int p=h[x];p;p=e[p].next){
				int y=e[p].to;
				if(dis[y]>dis[x]+1&&e[p].v){
					dis[y]=dis[x]+1;
					Q.push(y);
				}
			}
		}
		return dis[T]!=0x3f3f3f3f;
	}
	int dfs(int x,int Maxflow){
		if(x==T||!Maxflow)return Maxflow;
		int flow=0;
		for(int&p=cur[x];p&&Maxflow;p=e[p].next){
			int y=e[p].to;
			if(dis[y]!=dis[x]+1)continue;
			int ret=dfs(y,min(Maxflow,e[p].v));
			Maxflow-=ret;flow+=ret;
			e[p].v-=ret;e[e[p].pair].v+=ret;
		}
		return flow;
	}
	int Maxflow(int s,int t){
		int ans=0;
		S=s,T=t;
		while(bfs()){
			memcpy(cur,h,sizeof(h));
			ans+=dfs(S,INT_MAX);
		}
		return ans;
	}
	void solve(){
		for(int p=h[S];p;p=e[p].next){
			int x=e[p].to;
			for(int q=h[x];q;q=e[q].next){
				int y=e[q].to;
				if(y!=S&&!e[q].v)bl[x]=y;
			}
		}
	}
}
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]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			son[i][(a[i][j]-1)/m+1].push(a[i][j]);
	for(int i=1;i<=m;i++){
		int S=0,T=2*n+1;
		dinic::reset();
		for(int j=1;j<=n;j++)dinic::AddEdge(S,j,1),dinic::AddEdge(j+n,T,1);
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				if(son[j][k].size())
					dinic::AddEdge(j,k+n,1);
		assert(dinic::Maxflow(S,T)==n);
		dinic::solve();
		for(int j=1;j<=n;j++){
			b[j][i]=son[j][dinic::bl[j]-n].front();
			son[j][dinic::bl[j]-n].pop();
		}
	}
	memcpy(c,b,sizeof(c));
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<n;k++)
				if(c[k][i]>c[k+1][i])
					swap(c[k][i],c[k+1][i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cout<<b[i][j]<<" \n"[j==m];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cout<<c[i][j]<<" \n"[j==m];
	return 0;
}