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 <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
using namespace std;
int n,m,i,j,k,a[105][105],b[105][105],c[105][105],d[105][105],lk[105],s[105][105],vis[105];
int row(int x)
{
	return (x-1)/m+1;
}
int dfs(int x)
{
	if(vis[x])return 0;vis[x]=1;
	int i;fz1(i,n)if(s[x][i]){
		if(!lk[i]||dfs(lk[i])){
			lk[i]=x;return 1;
		}
	}return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	fz1(i,n)fz1(j,m){
		scanf("%d",&a[i][j]);
		b[i][j]=(i-1)*m+j;
	}
	fz1(i,m){
		memset(s,0,sizeof(s));
		fz1(j,n)fz(k,i,m){
			s[j][row(a[j][k])]=a[j][k];
		}
		memset(lk,0,sizeof(lk));
		fz1(j,n){
			memset(vis,0,sizeof(vis));
			if(!dfs(j))exit(-1);
		}
		fz1(j,n){
			c[lk[j]][i]=s[lk[j]][j];
			d[j][i]=s[lk[j]][j];
		}
		fz1(j,n){
			fz(k,i,m)if(s[lk[j]][j]==a[lk[j]][k]){
				swap(a[lk[j]][i],a[lk[j]][k]);
				break;
			}
		}
	}
	fz1(i,n){
		fz1(j,m){
			printf("%d%c",c[i][j],(j==m?'\n':' '));
		}
	}
	fz1(i,n){
		fz1(j,m){
			printf("%d%c",d[i][j],(j==m?'\n':' '));
		}
	}
	return 0;
}