첨단 가지 농장

밍구는 최첨단 가지 농장의 주인입니다. 가지 농장은 $N$개의 행과 $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$는 유일합니다.