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:
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=105;
int a[N][N],ans[N][N],n,m,dfn[N],match[N];
vector<int> g[N],to[N][N];

bool dfs(int x,int tg){
	if(dfn[x]==tg) return 0;
	dfn[x]=tg;
	for(int y:g[x]){
		if(!match[y]||dfs(match[y],tg)){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}

signed main(){
	read(n,m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(a[i][j]),to[i][(a[i][j]-1)/m+1].push_back(j);
	for(int k=1;k<=m;k++){
		for(int i=1;i<=n;i++) dfn[i]=match[i]=0,g[i].clear();
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(to[i][j].size()) g[i].push_back(j);
		for(int i=1;i<=n;i++) dfs(i,i);
		for(int i=1;i<=n;i++){
			int j=match[i];
			ans[j][k]=a[j][to[j][i].back()];
			to[j][i].pop_back();
		}
	}
	for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++,putchar(' ')) write(ans[i][j]);
	for(int j=1;j<=m;j++){
		int tp[N];
		for(int i=1;i<=n;i++) tp[i]=ans[i][j];
		sort(tp+1,tp+1+n);
		for(int i=1;i<=n;i++) ans[i][j]=tp[i];
	}
	for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++,putchar(' ')) write(ans[i][j]);
}