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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXH=100,MAXW=100;

int h,w;
int a[MAXH][MAXW];
int b[MAXH][MAXW];
int c[MAXH][MAXW];

vector<int> vals[MAXH][MAXH];

bool can[MAXH][MAXH];

int lmatch[MAXH],rmatch[MAXH];
bool ldone[MAXH];

bool augment(int x) {
	if(ldone[x]) return false; else ldone[x]=true;
	REP(xx,h) if(can[x][xx]&&(rmatch[xx]==-1||augment(rmatch[xx]))) { rmatch[xx]=x,lmatch[x]=xx; return true; }
	return false;
}

int maxmatch() {
	REP(x,h) lmatch[x]=rmatch[x]=-1,ldone[x]=false;
	int ret=0; REP(x,h) if(augment(x)) { ++ret; REP(xx,h) ldone[xx]=false; }
	return ret;
}


void solve() {
	REP(x,h) REP(xx,h) vals[x][xx].clear();
	REP(x,h) REP(y,w) vals[x][a[x][y]/w].PB(a[x][y]);
	REP(y,w) {
		REP(x,h) REP(xx,h) can[x][xx]=SZ(vals[x][xx])>0;
		//printf("can:\n"); REP(x,h) { REP(xx,h) printf("%c",can[x][xx]?'V':'.'); puts(""); }
		assert(maxmatch()==h);
		REP(x,h) { int xx=lmatch[x]; assert(xx!=-1&&SZ(vals[x][xx])!=0); int v=vals[x][xx].back(); vals[x][xx].pop_back(); b[x][y]=v; c[xx][y]=v; }
	}

}

void run() {
	scanf("%d%d",&h,&w);
	REP(x,h) REP(y,w) scanf("%d",&a[x][y]),--a[x][y];
	solve();
	REP(x,h) { REP(y,w) { if(y!=0) printf(" "); printf("%d",b[x][y]+1); } puts(""); }
	REP(x,h) { REP(y,w) { if(y!=0) printf(" "); printf("%d",c[x][y]+1); } puts(""); }
}

int main() {
	run();
	return 0;
}