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 FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (106)
ll n,m,grid[MAXN][MAXN],A[MAXN][MAXN],B[MAXN][MAXN];
vector<pi> v[MAXN];
int match[MAXN];//match[i]=index of edge from i
ll paired[MAXN];
bitset<MAXN>vis;
void bp() {
	mmst(match,-1);mmst(paired,-1);
	function<ll(ll)>dfs=[&](ll x){
		if(vis[x])return 0;
		vis[x]=1;
		ll co=0;
		for(auto i:v[x]){
			if(paired[i.f]==-1 || dfs(paired[i.f])){
				paired[i.f]=x;
				match[x]=co;
				return 1;
			}
			++ co;
		}
		return 0;
	};
	FOR(i,0,n-1)if(match[i]==-1)vis.reset(),dfs(i);
}
int main(){
	FAST
	cin>>n>>m;
	auto which_row=[&](ll x){
		return x/m;
	};
	FOR(i,0,n-1)FOR(j,0,m-1)cin>>grid[i][j],--grid[i][j];
	FOR(i,0,n-1)FOR(j,0,m-1){ll k=which_row(grid[i][j]);v[i].eb(k,grid[i][j]);}
	FOR(j,0,m-1){
		bp();
		FOR(i,0,n-1){
			assert(match[i]!=-1&&siz(v[i])>match[i]);
			A[i][j]=v[i][match[i]].s;
			v[i].erase(v[i].begin()+match[i]);
		}
	}
	FOR(i,0,n-1)assert(v[i].empty());
	FOR(i,0,n-1)FOR(j,0,m-1)cout<<A[i][j]+1<<" \n"[j==m-1];
	FOR(j,0,m-1){
		set<int>s;
		FOR(i,0,n-1)s.ins(which_row(A[i][j]));
		assert(s.size()==n);
	}
	FOR(j,0,m-1){
		FOR(i,0,n-1){
			B[which_row(A[i][j])][j]=A[i][j];
		}
	}
	FOR(i,0,n-1)FOR(j,0,m-1)cout<<B[i][j]+1<<" \n"[j==m-1];
}