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;
// Choose unvisited x and visited y as minimum vertex cover
// Also, Maximum Independent Set is the complement set of minimum vertex cover
template<int SZX,int SZY> struct BIPARTITE_MATCHING{
	int mx[SZX+1],my[SZY+1],lev[SZX+1],visx[SZX+1],visy[SZY+1];
	vector<int> e[SZX+1];
	bool dfs(int x){
		for(int y:e[x]){
			int w=my[y];
			if(w==-1||(lev[w]==lev[x]+1&&dfs(w)))
				return mx[x]=y,my[y]=x,true;
		}
		return lev[x]=-1,false;
	}
	void clear(int m){for(int i=0;i<=m;i++)	vector<int>().swap(e[i]);}
	void addedge(int x,int y){e[x].emplace_back(y);}
	int matching(int m,int n){
		fill(mx,mx+m+1,-1),fill(my,my+n+1,-1);
		for(int res=0;;){
			queue<int> q;
			for(int i=0;i<m;i++)
				if(mx[i]==-1)	q.emplace(i),lev[i]=0;
				else	lev[i]=-1;
			while(!q.empty()){
				int x=q.front();q.pop();
				for(int y:e[x]){
					int w=my[y];
					if(w!=-1&&lev[w]==-1)
						q.emplace(w),lev[w]=lev[x]+1;
				}
			}
			int delta=0;
			for(int i=0;i<m;i++)
				if(mx[i]==-1&&dfs(i))
					delta++;
			if(delta)	res+=delta;
			else	return res;
		}
		return 0;
	}
	int cover(int m,int n){
		int res=matching(m,n);
		fill(visx+1,visx+m+1,0), fill(visy+1,visy+n+1,0);
		queue<int> q;
		for(int i=1;i<=m;i++)	if(mx[i]==-1)	q.emplace(i),visx[i]=true;
		while(!q.empty()){
			int x=q.front();q.pop();
			for(int y:e[x]){
				visy[y]=true;
				int w=my[y];
				if(!visx[w])	q.emplace(w),visx[w]=true;
			}
		}
		return res;
	}
};
BIPARTITE_MATCHING<100,100> DS;

int a[100][100];
int used[100][100];
int mat[100][100];
int ans[100][100];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			cin>>a[i][j],a[i][j]--;
		}
	memset(used,-1,sizeof used);
	for(int c=0;c<m;c++){
		DS.clear(n);
		memset(mat,-1,sizeof mat);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
				int color = a[i][j]/m;
				if(used[i][j]==-1&&mat[i][color]==-1)
					DS.addedge(i,color),mat[i][color]=j;
			}
		DS.matching(n,n);
		for(int i=0;i<n;i++)
			used[i][mat[i][DS.mx[i]]]=c;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			ans[i][used[i][j]]=a[i][j];
	for(int i=0;i<n;i++,cout<<'\n')
		for(int j=0;j<m;j++)
			cout<<' '<<ans[i][j]+1;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			a[ans[i][j]/m][j]=ans[i][j];
	for(int i=0;i<n;i++,cout<<'\n')
		for(int j=0;j<m;j++)
			cout<<' '<<a[i][j]+1;
}