Advanced Eggplant Farm

Mingu owns an advanced eggplant farm. The farm is a grid of $N$ rows and $M$ columns, and an eggplant is planted in each of the $N \times M$ soil cells. Mingu noticed that eggplants that receive more water grow faster. To even out the sizes, he wants to give more water to the smaller eggplants.

To do this, the height of each soil cell can be changed to any non-negative integer. Water flows from higher ground to lower ground, so more water collects in the lower of two adjacent cells. If two adjacent cells have the same height, the same amount of water collects in each. Two cells are adjacent if they share a side.

To even out the sizes, for every pair of adjacent cells, the soil under the larger eggplant must be higher than the soil under the smaller one. If two adjacent eggplants have the same size, their soil heights must be equal.

Currently, every soil cell has height $0$. Changing the height of one cell to $h$ costs $h$ units of work, where $h$ is a non-negative integer. Find the height arrangement that evens out the sizes and has the minimum total work.

In other words, you are given a matrix $S$ of size $N \times M$ of positive integers, where $S_{i,j}$ is the size of the eggplant in row $i$, column $j$. Find a matrix $H$ of size $N \times M$ of non-negative integers, where $H_{i,j}$ is the height of the soil in row $i$, column $j$, that satisfies the following conditions.

• For all integers $i, j, k, l$ with $1 \le i, k \le N$, $1 \le j, l \le M$, and $|i-k| + |j-l| = 1$:
  • If $S_{i,j} < S_{k,l}$, then $H_{i,j} < H_{k,l}$.
  • If $S_{i,j} = S_{k,l}$, then $H_{i,j} = H_{k,l}$.
  • If $S_{i,j} > S_{k,l}$, then $H_{i,j} > H_{k,l}$.
• The sum of all elements of $H$ is minimal.

The first line contains the number of rows $N$ and the number of columns $M$, separated by a space. ($1 \le N, M \le 1\,000$)

Each of the next $N$ lines contains $M$ positive integers separated by spaces, which are the eggplant sizes in that row. The $j$-th number on the $i$-th line is the eggplant size $S_{i,j}$ in row $i$, column $j$. ($1 \le S_{i,j} \le 10^9$)

Print $N$ lines, each containing $M$ non-negative integers separated by spaces.

The $j$-th number on the $i$-th line is $H_{i,j}$, the soil height in row $i$, column $j$, in the arrangement with the minimum total work.

The matrix $H$ that answers the problem is unique.