31633번 - 첨단 가지 농장

문제

밍구는 최첨단 가지 농장의 주인입니다. 가지 농장에는 $N$개의 행과 $M$개의 열로 이루어진 격자 위 $N \times M$칸의 토양에 가지가 심겨 있습니다. 밍구는 최근 물을 많이 받은 가지들이 더 빨리 자란다는 사실을 깨달았습니다. 밍구는 가지들의 크기를 균일하게 만들기 위해 크기가 작은 가지들에 더 많은 물을 주려고 합니다.

이를 위해 가지 농장에서는 토양의 높이를 임의의 음이 아닌 정수로 변경할 수 있습니다. 물은 높이가 높은 곳에서 낮은 곳으로 흐르게 되어 인접한 두 칸의 토양 중 높이가 높은 토양보다 높이가 낮은 토양에 더 많은 양의 물이 모이게 됩니다. 인접한 두 토양의 높이가 같으면 같은 양의 물이 모이게 됩니다. 단, 두 칸의 토양이 한 변을 공유할 때 서로 인접하였다고 합니다.

가지의 크기를 균일하게 만들기 위해서는 모든 인접한 두 칸의 토양 중 큰 가지가 있는 토양의 높이가 작은 가지가 있는 토양보다 높아야 합니다. 인접한 두 칸의 토양에 있는 가지의 크기가 같다면 두 토양의 높이가 같아야 합니다.

현재 모든 토양의 높이는 0ドル$입니다. 토양 한 칸의 높이를 $h$로 변경하려면 $h$만큼의 일을 해야 합니다. 이때, $h$는 음이 아닌 정수입니다. 가지의 크기를 균일하게 만드는 토양의 높이 배치 중에서 해야 하는 일의 총합이 최소가 되는 토양의 높이 배치를 구하세요.

다시 말해, 각 가지의 크기를 의미하는 크기 $N \times M$의 양의 정수의 행렬 $S$가 주어질 때, 다음의 조건을 만족시키고 각 토양의 높이 배치를 나타내는 크기 $N \times M$의 음이 아닌 정수의 행렬 $H$를 구하려고 합니다.

• 1ドル \le i, k \le N,ドル 1ドル \le j, l \le M,ドル $|i-k| + |j-l| = 1$인 모든 정수 $i,ドル $j,ドル $k,ドル $l$에 대해서 다음 조건을 만족시켜야 합니다.
  • $S_{i, j} < S_{k, l}$이면 $H_{i, j} < H_{k, l}$입니다.
  • $S_{i, j} = S_{k, l}$이면 $H_{i, j} = H_{k, l}$입니다.
  • $S_{i, j} > S_{k, l}$이면 $H_{i, j} > H_{k, l}$입니다.
• $H$의 모든 원소의 합이 최소여야 합니다.

입력

첫 번째 줄에 농장의 세로 길이 $N$과 농장의 가로 길이 $M$이 공백으로 구분되어 주어집니다. $(1 \le N, M \le 1,000円)$

다음 $N$개 줄 각각에 각 행에 있는 가지들의 크기를 나타내는 $M$개의 양의 정수가 공백으로 구분되어 주어집니다. 그중 $i$번째 줄의 $j$번째 수는 $i$행 $j$열에 있는 가지의 크기 $S_{i, j}$를 나타냅니다. $(1 \le S_{i, j} \le 10^9)$

출력

$N$개의 줄 각각에 $M$개의 음이 아닌 정수를 공백으로 구분하여 출력합니다.

$i$번째 줄의 $j$번째 수는 해야 하는 일의 총합이 최소가 되는 토양의 높이 배치에서 $i$행 $j$열 토양의 높이, $H_{i, j}$여야 합니다.

답이 되는 행렬 $H$는 유일합니다.

제한

힌트