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>
#define ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
struct edge{int v,nxt,f;};
class Graph{
	edge e[200100];
	int tot,head[1010],cur[1010],b[1010];
public:
	int t;
	Graph(){tot=1;memset(head,0,sizeof(head));}
	void add(int x,int y,int z){
		e[++tot]={y,head[x],z};
		head[x]=tot;
		e[++tot]={x,head[y],0};
		head[y]=tot;
	}
	bool bfs(){
		memset(b,0,sizeof(b));b[0]=1;
		queue<int> q;q.push(0);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=head[u];i;i=e[i].nxt)
				if(e[i].f&&!b[e[i].v]){
					b[e[i].v]=b[u]+1;
					q.push(e[i].v);
				}
		}
		return b[t];
	}
	int dfs(int x,int flow){
		if(x==t||!flow) return flow;
		int f=flow,tmp;
		for(int &i=cur[x];i;i=e[i].nxt)
			if(b[e[i].v]==b[x]+1&&(tmp=dfs(e[i].v,min(e[i].f,f)))){
				f-=tmp;
				e[i].f-=tmp;e[i^1].f+=tmp;
				if(!f) break;
			}
		return flow-f;
	}
	int Dinic(){
		int ans=0;
		while(bfs()){
			memcpy(cur,head,sizeof(cur));
			ans+=dfs(0,100000000);
		}
		return ans;
	}
	int chk(int x){
		for(int i=head[x];i;i=e[i].nxt)
			if(e[i].v&&!e[i].f) return e[i].v;
	}
};
int n,m,a[110][110],ans1[110][110],ans2[110][110];
stack<int> h[110][110];
int main(){
	read(n);read(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			int x;read(x);
			h[i][(x-1)/m+1].push(x);
		}
	for(int k=1;k<=m;k++){
		Graph G;G.t=2*n+1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(h[i][j].size()) G.add(i,j+n,1);
		for(int i=1;i<=n;i++)
			G.add(0,i,1),G.add(i+n,G.t,1);
		G.Dinic();
		for(int i=1;i<=n;i++){
			int p=G.chk(i)-n;
			int now=h[i][p].top();h[i][p].pop();
			ans1[i][k]=now;
			ans2[p][k]=now;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cout<<ans1[i][j]<<" \n"[j==m];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cout<<ans2[i][j]<<" \n"[j==m];
	return 0;
}