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;
#define N 210
#define M 200010
#define inf 2147483647
#define col(x) (((x-1)/m)+1)
inline int read() {
    int x=0;
    char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}
int tot=1;
int fir[N],nex[M],got[M],tak[M];
inline void AddEdge(int x,int y,int z) { 
    nex[++tot]=fir[x],fir[x]=tot,got[tot]=y,tak[tot]=z; 
} 
int a[N][N],b[N][N];
vector <int> v[N][N];
int dep[N],que[N];
inline int bfs(int s,int t) {
	memset(dep,0,sizeof(dep));
	int l=1,r=1;
	dep[s]=1,que[1]=s;
	while (l<=r) {
		int x=que[l++];
		for (int i=fir[x];i;i=nex[i]) {
			int y=got[i];
			if (dep[y] || !tak[i]) continue;
			dep[y]=dep[x]+1,que[++r]=y;
		}
	}
	return dep[t];
}
inline int dfs(int x,int t,int flow) {
	int rest=flow;
	if (x==t) return flow;
	for (int i=fir[x];i && rest;i=nex[i]) {
		int y=got[i];
		if (!tak[i] || dep[y]!=dep[x]+1) continue;
		int k=dfs(y,t,min(rest,tak[i]));
		if (!k) dep[y]=0;
		tak[i]-=k,tak[i^1]+=k,rest-=k;
	}
	return flow-rest;
}
int main() {
    int n=read(),m=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            a[i][j]=read();
            v[i][col(a[i][j])].push_back(a[i][j]);
        }
    for (int w=1;w<=m;w++) {
        tot=1;
        memset(fir,0,sizeof(fir));
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++) if (v[i][j].size()) {
                    AddEdge(i,j+n,1),AddEdge(j+n,i,0);
                }
        int s=2*n+1,t=s+1;
        for (int i=1;i<=n;i++)
            AddEdge(s,i,1),AddEdge(i,s,0),
            AddEdge(t,i+n,0),AddEdge(i+n,t,1);
        while (bfs(s,t)) dfs(s,t,inf);
        for (int i=1;i<=n;i++) {
            for (int j=fir[i];j;j=nex[j]) {
                if (got[j]>n && !tak[j]) b[i][w]=v[i][got[j]-n].back(),v[i][got[j]-n].pop_back();
            }
        }
    }
    for (int i=1;i<=n;i++,putchar('\n'))
        for (int j=1;j<=m;j++) printf("%d ",a[col(b[i][j])][j]=b[i][j]);
    for (int i=1;i<=n;i++,putchar('\n'))
        for (int j=1;j<=m;j++) printf("%d ",a[i][j]);
    return 0;
}