Nearest White Pixel Distance

You are given an ancient display consisting of \(N \times M\) pixels. Each pixel is represented by a binary value: \(0\) denotes black and \(1\) denotes white. The pixel at row \(x\) and column \(y\) is denoted by \(P(x,y)\). When the computer issues a command to display a 2D \(01\) matrix, the corresponding pixels light up white or remain black based on the values in the matrix.

However, due to an unknown reason, a black pixel (\(0\)) is influenced by the nearby white pixels. The closer a white pixel is, the stronger the influence. The distance between two pixels \(P_1(x_1,y_1)\) and \(P_2(x_2,y_2)\) is defined using the Manhattan distance: \[ D(P_1, P_2) = |x_1 - x_2| + |y_1 - y_2| \]

Your task is to compute, for every pixel on the screen, the shortest distance to any white pixel. It is guaranteed that there is at least one white pixel in the matrix.

Example:

If the screen is \(3 \times 4\) and the command matrix is:

[ \begin{pmatrix} 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 1 \ 0 & 1 & 1 & 0 \end{pmatrix} ]

Then the pixel at \(P(1,1)\) has a minimum distance of \(3\) to a white pixel and the pixel \(P(3,2)\) (which is white) has a distance of \(0\).

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of rows and columns, respectively.

The following \(N\) lines each contain \(M\) integers (each either \(0\) or \(1\)), representing the state of each pixel.

outputFormat

Output the resulting \(N \times M\) matrix where each element is the minimum Manhattan distance from that pixel to any white pixel. Print each row in a new line with the distances separated by a single space.

sample

3 4
0 0 0 1
0 0 1 1
0 1 1 0

3 2 1 0
2 1 0 0
1 0 0 1