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 rep(i,s,t) for(int i=s;i<t;i++)
#define MAXNUM 111
vector<int> e[MAXNUM];
bool isusedl[MAXNUM],isusedr[MAXNUM];
int matchx[MAXNUM], matchy[MAXNUM];
int n;
bool rematch(int now)
{
    isusedl[now]=1;
    for(int k:e[now])
        if(!isusedr[k])
        {
            isusedr[k] = 1;
            int g = matchy[k];
            if (!g || (rematch(g)))
            {
                matchx[now] = k;
                matchy[k] = now;
                return 1;
            }
        }
    return 0;
}
int getmatch()
{
    int res = 0;
    memset(matchx, 0, sizeof(matchx));
    memset(matchy, 0, sizeof(matchy));
    for (int i = 1; i <= n; i++)
    {
        if (matchx[i])
            continue;
        memset(isusedr, 0, sizeof(isusedr));
        res += rematch(i);
    }
    return res;
}
int mat[111][111];
int main()
{
    int m;scanf("%d%d",&n,&m);
    rep(i,1,n+1)rep(j,1,m+1)scanf("%d",&mat[i][j]);
    rep(i,1,m+1)
    {
        rep(j,1,n+1)e[j].clear();
        rep(j,1,n+1)rep(k,i,m+1)
        e[(mat[j][k]-1)/m+1].push_back(j);
        getmatch();
        rep(j,1,n+1)
        {
            int k=matchx[j];
            rep(x,i,m+1)
            if((mat[k][x]-1)/m+1==j)
            {
                swap(mat[k][i],mat[k][x]);
                break;
            }
        }
    }
    rep(i,1,n+1){
        rep(j,1,m+1)printf("%d ",mat[i][j]);
        puts("");
    }
    rep(i,1,n+1)rep(j,1,m+1)
    {
        rep(k,i,n+1)
        if((mat[k][j]-1)/m+1==i)
        {
            swap(mat[k][j],mat[i][j]);
            break;
        }
    }
    rep(i,1,n+1){
        rep(j,1,m+1)printf("%d ",mat[i][j]);
        puts("");
    }
}