Topographic Prominence

As we all know, the Earth is a square grid consisting of $R$ rows, numbered from $1$ to $R$, and $C$ columns numbered from $1$ to $C$. The cell in row $i$ and column $j$ has an elevation of $H_{i,j}$. In topography, there is a concept called prominence which is a measure of how high a point rises above the surrounding terrain. Informally, it is the least drop in height required to go from a certain point to a higher point. Formally, it is defined as follows:

• Two cells are adjacent if they are in the same row and are exactly one column apart, or if they are in the same column and are exactly one row apart.
• A walk is a sequence of cells where each cell except the last is adjacent to the following one.
• If a cell $A$ has the highest elevation in the grid, its prominence is infinite.
• Otherwise, let $X$ be the highest elevation such that there exists a walk from $A$ to a cell whose elevation is strictly greater than $A$’s, where every cell in the walk has an elevation greater or equal to $X$. The prominence of cell $A$ is equal to its elevation minus $X$.

The diagram below provides a stylistic representation of how the prominence of two points, peaks B and C, is found. The horizontal lines represent the value of $X$ for the two peaks. The lengths of the vertical arrows correspond to the prominence of the peaks.

Your task is to find the prominence of all cells in the grid.

Input

The first line of input contains two integers: $R$ and $C$.

The next $R$ lines of input each contain $C$ integers. The $j$-th integer $(1 ≤ j ≤ C)$ on the $i$-th of these lines $(1 ≤ i ≤ R)$ is $H_{i,j}$.

Output

You should output $R$ lines of input each containing $C$ integers. The $j$-th integer $(1 ≤ j ≤ C)$ on the $i$-th of these lines $(1 ≤ i ≤ R)$ should be the prominence of cell $(i, j)$. If its prominence is infinite, output $-1$ for it.

Constraints

• $1 \le R ≤ 1,000$
• $1 ≤ R × C ≤ 100,000$
• $1 ≤ H_{i,j} ≤ 1,000,000$ for all $1 ≤ i ≤ R, 1 ≤ j ≤ C$

Subtasks

• Subtask 1 (14%): $R = 1, C ≤ 100$
• Subtask 2 (15%): $R × C ≤ 100$
• Subtask 3 (16%): $R × C ≤ 1000$
• Subtask 4 (12%): $R = 1$
• Subtask 5 (14%): $H_{i,j} ≤ 10$ for all $1 ≤ i ≤ R, 1 ≤ j ≤ C$
• Subtask 6 (17%): All $H_{i,j}$ are distinct
• Subtask 7 (12%): No further constraints

Notes

This question has a lot of subtasks, some of which may be significantly easier to solve than the full solution!

Subtask scoring is cumulative - So for example, if you solve only Subtask 1 in one submission and only Subtask 2 in another submission, you still will have gained 29% for your score.

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.11 (PyPy 7.3.19) when submitting as this will generally make your code run faster. Although it should be noted that PyPy may be slower when using recursion.

Sample Explanations

Sample 1

In the first example below:

• The first cell from left has the highest height of any cell and so has infinite prominence.
• The second, fourth and sixth cells from left all neighbour a cell higher than them. Hence no drop is necessary to reach a higher point and their prominences are all $0$.
• The third cell from left can reach a higher cell by going right twice. The lowest height encountered is $3$, which is optimal, so the prominence of this cell is $4-3=1$.
• The fifth cell from left must go left four times to reach a higher cell. The lowest height encountered is $2$, giving it a prominence of $3$.

Sample 2

In the second example below:

• Cell $(1, 1)$, i.e. top left, has infinite prominence.
• Cells $(1, 2), (2, 1), (2, 3), (3, 1)$ and $(3, 2)$ all neighbour a cell higher than them so their prominences are all $0$.
• Cell $(1, 3)$ can reach cell $(1, 1)$ by going down, left, left and up. The lowest height encountered on this walk is $3$, giving us a drop of $5$. No walk to a higher cell with a smaller drop exists, hence the prominence of this cell is $5$.
• Cell $(2, 2)$ achieves a drop of $3$ by going left and up.
• Cell $(3, 3)$ achieves a drop of $1$ by going left and up.