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 N=105;
typedef pair<int,int>pii;
struct graph{
	static const int N=210,M=11000;
	struct edge{int to,next,f;}e[M<<1];
	int h[N],cur[N],xb;
	inline void addedge(int x,int y,int z){
		e[++xb]=(edge){y,h[x],z};h[x]=xb;
		e[++xb]=(edge){x,h[y],0};h[y]=xb;
	}
	int S,T,d[N],n;
	inline bool bfs(){
		static int q[N];int t=0,w=1;q[1]=S;
		memset(d+1,0,n<<2);d[S]=1;
		for(;t<w;){
			int u=q[++t];
			for(int i=h[u];i;i=e[i].next)if(e[i].f && !d[e[i].to])
				d[e[i].to]=d[u]+1,q[++w]=e[i].to;
		}
		return d[T];
	}
	int dfs(int x,int f){
		if(x==T)return f;
		int ans=0,&i=cur[x],t;
		for(;i;i=e[i].next)if(e[i].f && d[e[i].to]==d[x]+1){
			if(t=dfs(e[i].to,min(f,e[i].f))){
				ans+=t,e[i].f-=t;e[i^1].f+=t;f-=t;
				if(!f)break;
			}
		}
		return ans;
	}
	inline int dinic(int s,int t){
		int ans=0;S=s;T=t;
		for(;bfs();ans+=dfs(s,1<<30))memcpy(cur+1,h+1,n<<2);
		return ans;
	}
}g;
int n,m,x,i,j,k,l,b[N][N],c[N][N],d[N];
vector<int>a[N];
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)for(j=0,a[i].resize(m);j<m;++j)scanf("%d",&a[i][j]);;
	for(i=1;i<=m;++i){
		g.xb=1;g.n=n*2+2;memset(g.h+1,0,g.n<<2);
		for(j=1;j<=n;++j){
			g.addedge(g.n-1,j,1);g.addedge(j+n,g.n,1);
			for(k=0;k<=m-i;++k)g.addedge(j,(a[j][k]-1)/m+1+n,1);
		}
		assert(g.dinic(g.n-1,g.n)==n);
		for(j=1;j<=n;++j){
			for(k=g.h[j];g.e[k].f || g.e[k].to==g.n-1;k=g.e[k].next);
			for(l=0;(a[j][l]-1)/m+1!=g.e[k].to-n;++l);
			b[j][i]=a[j][l];a[j].erase(a[j].begin()+l);
		}
	}
	for(i=1;i<=n;++i)memcpy(c[i]+1,b[i]+1,m<<2);
	for(i=1;i<=m;++i){
		for(j=1;j<=n;++j)d[j]=c[j][i];
		sort(d+1,d+n+1);
		for(j=1;j<=n;++j)c[j][i]=d[j];
	}
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)printf("%d%c",b[i][j],j==m?'\n':' ');
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)printf("%d%c",c[i][j],j==m?'\n':' ');
	return 0;
}