Power Game

Jonathan is excited about the new sensation of the moment: the Power Game. This game is played on a grid with $N$ rows and $M$ columns, where each cell contains a monster. The monster in row $i$ and column $j$ has power $P_{i,j}$.

At the start of the game, Jonathan chooses one of the $N \times M$ monsters to play. The monster chosen by Jonathan becomes the hero of the game and starts the game with the power indicated in its cell. Jonathan can move the hero orthogonally (that is, up, down, right, or left) within the grid as long as the hero is alive. The hero cannot leave the grid, but can visit the same cell multiple times.

Every time the hero enters a cell with a living monster, a battle occurs between the hero and the monster in the cell. The hero wins the battle if, and only if, its power is greater than or equal to the monster's power. Otherwise, the hero dies and the game ends in game over. Every time the hero wins a battle, the defeated monster dies (i.e., the cell no longer contains any monster) and, as a reward, the monster's power is added to the hero's power (i.e., if the hero kills the monster in cell $(i, j)$, the hero's power increases by $P_{i,j}$).

Jonathan realized that the game might be unfair: even if he plays optimally, depending on his choice of hero, it might be possible to kill all the monsters, just some, or even none.

Determined to “platinum” the game, Jonathan needs to know the maximum power each hero can reach (i.e., the maximum possible power that can be achieved when starting the game in each cell of the grid) if the game is played optimally. Fortunately, he discovered that the students of OBI (Organization of Good Programmers) recently solved the Game of Life, his third favorite game (after the Power Game and the Racing Game, of course), so he asked for your help again! Determine, for each hero, the maximum power they can reach if Jonathan plays optimally.

Input

The first line of input contains two integers $N$ and $M$, the number of rows and the number of columns of the grid, respectively.

The next $N$ lines contain $M$ integers each. The $j$-th integer of the $i$-th line contains the power $P_{i,j}$ of the monster in the $i$-th row and $j$-th column.

Output

Your program should print $N$ lines, each containing $M$ integers. The $j$-th integer of the $i$-th line should be the maximum power Jonathan can reach if he chooses as the hero the monster from cell $(i, j)$ and plays optimally.

Constraints

• $1 \leq N \leq 100,000$
• $1 \leq M \leq 100,000$
• $1 \leq N \times M \leq 100,000$
• $1 \leq P_{i,j} \leq 1,000,000,000$ for all $1 \leq i \leq N$ and $1 \leq j \leq M$

Attention: Note that it is not possible to declare $100,000 × 100,000$ integers (with matrix, vector, etc.) without exceeding the memory limit (this would cause errors in the program as it would attempt to use tens of GB of memory). Pay attention to the limit $N × M \leq 100,000$, which ensures that the grid will always have at most 100,000 cells.