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;

struct BipartiteGraph
{
	vector<int> leftMatch, rightMatch, lab, seen;
	vector<vector <int>> a;
	int m, n;

	BipartiteGraph() {}
	BipartiteGraph(int m, int n)
	{
		this -> m = m;
		this -> n = n;
		a = vector<vector<int>>(m);
		leftMatch = vector<int>(n, -1);
		rightMatch = vector<int>(m, -1);
		lab = vector<int>(m, -1);
		seen = vector<int>(n, 0);
	}

	void addEdge(int x, int y)
	{
		a[x].push_back(y);
	}

	int findMatch(int x)
	{
		for (int i = 0; i < int(a[x].size()); i++)
		{
			int y = a[x][i];
			if (seen[y]) continue;
			seen[y] = 1;
			if (leftMatch[y] < 0 || findMatch(leftMatch[y]))
			{
				leftMatch[y] = x; rightMatch[x] = y;
				return 1;
			}
		}
		return 0;
	}

	int maxMatching()
	{
		for (int i = 0; i < m; i++) lab[i] = i;
		while (1)
		{
			int lastM = m;
			for (int i = 0; i < n; i++) seen[i] = 0;
			for (int i = m - 1; i >= 0; i--)
				if (findMatch(lab[i])) lab[i] = lab[--m];
			if (lastM == m) break;
		}
		int match = 0;
		for (int i = 0; i < n; i++) match += (leftMatch[i] >= 0);
		return match;
	}
};

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int m, n, a[100][100], b[100][100];
  cin >> m >> n;
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
    {
      cin >> a[i][j];
      --a[i][j];
    }

  for (int col = 0; col < n; col++)
  {
    BipartiteGraph g(m, m);
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        if (a[i][j] >= 0)
          g.addEdge(i, a[i][j] / n);

    assert(g.maxMatching() == m);
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        if (a[i][j] >= 0 && a[i][j] / n == g.rightMatch[i])
        {
          b[i][col] = a[i][j];
          a[i][j] = -1;
          break;
        }
  }

  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      cout << b[i][j] + 1 << " \n"[j == n - 1];

  for (int j = 0; j < n; j++)
    for (int i = 0; i < m; i++)
      for (int ii = i + 1; ii < m; ii++)
        if (b[i][j] > b[ii][j])
          swap(b[i][j], b[ii][j]);

  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      cout << b[i][j] + 1 << " \n"[j == n - 1];
}