Rearrange
Contest: Codeforces Round 659 (Div. 1)
Difficulty rating: 2800
Tags: brute force, constructive algorithms, graphs, greedy, sortings

Koa the Koala has a matrix $$$A$$$ of $$$n$$$ rows and $$$m$$$ columns. Elements of this matrix are distinct integers from $$$1$$$ to $$$n \cdot m$$$ (each number from $$$1$$$ to $$$n \cdot 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}, \ldots, M_{im} ]$$$ for all $$$i$$$ ($$$1 \le i \le n$$$).
- The $$$j$$$-th column of $$$M$$$ is defined as $$$C_j(M) = [ M_{1j}, M_{2j}, \ldots, M_{nj} ]$$$ for all $$$j$$$ ($$$1 \le j \le 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)), \ldots, \max(R_n(A)) \}$$$
- $$$Y = \{ \max(C_1(A)), \max(C_2(A)), \ldots, \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 \cdot 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 \le i \le n$$$)
- $$$C_j(A')$$$ is bitonic for all $$$j$$$ ($$$1 \le j \le m$$$)

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

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

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 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 \le A_{ij} \le n \cdot m$$$) of matrix $$$A$$$. It is guaranteed that every number from $$$1$$$ to $$$n \cdot m$$$ appears exactly once among elements of the matrix.

Output format:
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 \cdot 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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Let's analyze the first sample:

For matrix $$$A$$$ we have:

- $$$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:

- 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 \})$$$

Example input:
3 3
3 5 6
1 7 9
4 8 2

Example output:
9 5 1
7 8 2
3 6 4

Example input:
2 2
4 1
3 2

Example output:
4 1
3 2

Editorial:
Let $$$A$$$ be a matrix of size $$$n \cdot m$$$ that is formed by a permutation of elements from $$$1$$$ to $$$n \cdot m$$$. Find the maximum element on each row and column (i.e. the spectrum)
Now we are going to build the answer adding numbers one by one in decreasing order. We start with an empty 2 dimensional matrix (both dimensions have length 0) and at the end of each iteration the following invariants will be maintained on the matrix:
1. All elements processed are inside of the matrix.
2. Each row and column is bitonic.
3. The horizontal/vertical spectrum of this matrix is a subset of the expected horizontal/vertical spectrum.
In addition we are keeping a queue with all positions in the matrix that doesn't contain any element yet. At the end of each iteration the following invariants will be maintained on the queue:
• Let $$$A$$$ be a position on the queue and $$$B$$$ a position that contains a value that belongs to the horizontal spectrum in the matrix such that $$$A$$$ and $$$B$$$ are in the same row, then all positions between $$$A$$$ and $$$B$$$ have already an element in the matrix or occur in the queue before $$$A$$$.
• Let $$$A$$$ be a position on the queue and $$$B$$$ a position that contains a value that belongs to the vertical spectrum in the matrix such that $$$A$$$ and $$$B$$$ are in the same column, then all positions between $$$A$$$ and $$$B$$$ have already an element in the matrix or occur in the queue before $$$A$$$.
In the end, invariants on the matrix guarantee that all elements are placed, each row and column consist in a bitonic sequence as required and the spectrums are equal to the expected spectrums.
Let's prove each invariant on the matrix is kept:
1. Clearly on each step a different element is placed on the matrix on an empty position, we should only show that the operation pop element from Queue doesn't fail with Queue empty. Say the current element is $$$t$$$, so the matrix is filled with elements larger than $$$t$$$. Now we know that in original matrix there were at least $$$n-x$$$ rows with maximums less than t and at least m-y columns with maximums less than $$$t$$$, so there could be at most $$$x \cdot y$$$ elements greater or equal than t but there are $$$x \cdot y+1$$$ already.
2. On each row and column the first element added is the maximum and then elements are added in each direction starting from it toward each edge, since elements are processed from largest to smallest then each row and column is bitonic.
3. The first element added on each row and column is the maximum, and we only add it if it is part of the expected spectrum.
Time complexity: $$$O(n \cdot m)$$$