Problem: Koa the Koala has a matrix A of n rows and m columns. Elements of this matrix are distinct integers from 1 to n ⋅ m (each number from 1 to n ⋅ m appears exactly once in the matrix).

For any matrix M of n rows and m columns let's define the following:

  * The i-th row of M is defined as R_i(M) = [ M_{i1}, M_{i2}, …, M_{im} ] for all i (1 ≤ i ≤ n). 
  * The j-th column of M is defined as C_j(M) = [ M_{1j}, M_{2j}, …, M_{nj} ] for all j (1 ≤ j ≤ m). 



Koa defines S(A) = (X, Y) as the spectrum of A, where X is the set of the maximum values in rows of A and Y is the set of the maximum values in columns of A.

More formally:

  * X = \{ max(R_1(A)), max(R_2(A)), …, max(R_n(A)) \} 
  * Y = \{ max(C_1(A)), max(C_2(A)), …, max(C_m(A)) \}



Koa asks you to find some matrix A' of n rows and m columns, such that each number from 1 to n ⋅ m appears exactly once in the matrix, and the following conditions hold:

  * S(A') = S(A) 
  * R_i(A') is bitonic for all i (1 ≤ i ≤ n) 
  * C_j(A') is bitonic for all j (1 ≤ j ≤ m) 

An array t (t_1, t_2, …, t_k) is called bitonic if it first increases and then decreases.

More formally: t is bitonic if there exists some position p (1 ≤ p ≤ k) such that: t_1 < t_2 < … < t_p > t_{p+1} > … > t_k.

Help Koa to find such matrix or to determine that it doesn't exist.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 250) — the number of rows and columns of A.

Each of the ollowing n lines contains m integers. The j-th integer in the i-th line denotes element A_{ij} (1 ≤ A_{ij} ≤ n ⋅ m) of matrix A. It is guaranteed that every number from 1 to n ⋅ m appears exactly once among elements of the matrix.

Output

If such matrix doesn't exist, print -1 on a single line.

Otherwise, the output must consist of n lines, each one consisting of m space separated integers — a description of A'.

The j-th number in the i-th line represents the element A'_{ij}.

Every integer from 1 to n ⋅ m should appear exactly once in A', every row and column in A' must be bitonic and S(A) = S(A') must hold.

If there are many answers print any.

Examples

Input


3 3
3 5 6
1 7 9
4 8 2


Output


9 5 1
7 8 2
3 6 4


Input


2 2
4 1
3 2


Output


4 1
3 2


Input


3 4
12 10 8 6
3 4 5 7
2 11 9 1


Output


12 8 6 1
10 11 9 2
3 4 5 7

Note

Let's analyze the first sample:

For matrix A we have:

    * Rows: 
      * R_1(A) = [3, 5, 6]; max(R_1(A)) = 6 
      * R_2(A) = [1, 7, 9]; max(R_2(A)) = 9 
      * R_3(A) = [4, 8, 2]; max(R_3(A)) = 8 

    * Columns: 
      * C_1(A) = [3, 1, 4]; max(C_1(A)) = 4 
      * C_2(A) = [5, 7, 8]; max(C_2(A)) = 8 
      * C_3(A) = [6, 9, 2]; max(C_3(A)) = 9 

  * X = \{ max(R_1(A)), max(R_2(A)), max(R_3(A)) \} = \{ 6, 9, 8 \} 
  * Y = \{ max(C_1(A)), max(C_2(A)), max(C_3(A)) \} = \{ 4, 8, 9 \} 
  * So S(A) = (X, Y) = (\{ 6, 9, 8 \}, \{ 4, 8, 9 \}) 



For matrix A' we have:

    * Rows: 
      * R_1(A') = [9, 5, 1]; max(R_1(A')) = 9 
      * R_2(A') = [7, 8, 2]; max(R_2(A')) = 8 
      * R_3(A') = [3, 6, 4]; max(R_3(A')) = 6 

    * Columns: 
      * C_1(A') = [9, 7, 3]; max(C_1(A')) = 9 
      * C_2(A') = [5, 8, 6]; max(C_2(A')) = 8 
      * C_3(A') = [1, 2, 4]; max(C_3(A')) = 4 

  * Note that each of this arrays are bitonic. 
  * X = \{ max(R_1(A')), max(R_2(A')), max(R_3(A')) \} = \{ 9, 8, 6 \} 
  * Y = \{ max(C_1(A')), max(C_2(A')), max(C_3(A')) \} = \{ 9, 8, 4 \} 
  * So S(A') = (X, Y) = (\{ 9, 8, 6 \}, \{ 9, 8, 4 \}) 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
const int infinity = (int)1e9 + 42;
const int64_t llInfinity = (int64_t)1e18 + 256;
const int module = (int)1e9 + 7;
const long double eps = 1e-8;
mt19937_64 randGen(system_clock().now().time_since_epoch().count());
inline void raiseError(string errorCode) {
  cerr << "Error : " << errorCode << endl;
  exit(42);
}
signed main() {
  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<vector<int> > a(n, vector<int>(m));
  vector<tuple<int, int, int> > cells;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> a[i][j];
      cells.emplace_back(a[i][j], i, j);
    }
  }
  sort(begin(cells), end(cells));
  reverse(begin(cells), end(cells));
  set<pair<int, int> > queued;
  vector<char> hr(n), hc(m);
  int h = 0, w = 0;
  vector<vector<int> > r(n, vector<int>(m));
  vector<int> rowLe(n, -1), rowRi(n, -1);
  vector<int> colLe(m, -1), colRi(m, -1);
  auto canAdd = [&](int x, int y) {
    return (rowLe[x] < 0 || y == rowLe[x] - 1 || y == rowRi[x] + 1) &&
           (colLe[y] < 0 || x == colLe[y] - 1 || x == colRi[y] + 1);
  };
  auto doAdd = [&](int x, int y) {
    if (rowLe[x] < 0) {
      rowLe[x] = rowRi[x] = y;
    }
    if (colLe[y] < 0) {
      colLe[y] = colRi[y] = x;
    }
    rowLe[x] = min(rowLe[x], y);
    rowRi[x] = max(rowRi[x], y);
    colLe[y] = min(colLe[y], x);
    colRi[y] = max(colRi[y], x);
  };
  for (auto [val, x, y] : cells) {
    if (!hr[x] && !hc[y]) {
      if (h != 0 && w != 0) {
        queued.emplace(h, w - 1);
        queued.emplace(h - 1, w);
      }
      r[h][w] = val;
      doAdd(h, w);
      hr[x] = hc[y] = true;
      ++h;
      ++w;
      continue;
    }
    if (!hr[x]) {
      assert(h != 0);
      if (w > 1 && r[h - 1][w - 2] != 0) {
        queued.emplace(h, w - 2);
      }
      r[h][w - 1] = val;
      doAdd(h, w - 1);
      hr[x] = true;
      ++h;
      continue;
    }
    if (!hc[y]) {
      assert(w != 0);
      if (h > 1 && r[h - 2][w - 1] != 0) {
        queued.emplace(h - 2, w);
      }
      r[h - 1][w] = val;
      doAdd(h - 1, w);
      hc[y] = true;
      ++w;
      continue;
    }
    if (queued.empty()) {
      cout << -1 << endl;
      return 0;
    }
    {
      auto [x, y] = *queued.begin();
      queued.erase(queued.begin());
      doAdd(x, y);
      r[x][y] = val;
      const int dx[4] = {-1, 1, 0, 0};
      const int dy[4] = {0, 0, -1, 1};
      for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (0 <= nx && nx < h && 0 <= ny && ny < w && canAdd(nx, ny) &&
            r[nx][ny] == 0) {
          queued.emplace(nx, ny);
        }
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cout << r[i][j] << " ";
    }
    cout << "\n";
  }
  cout << "\n";
  return 0;
}