Nearest White Pixel Distance

We are given an $n \times m$ monochrome bitmap that contains at least one white pixel. Each pixel is represented as a character, where '1' denotes a white pixel and '0' denotes a black pixel. We denote the pixel in the $i$-th row and $j$-th column as $(i,j)$. The Manhattan distance between two pixels $p_1=(i_1,j_1)$ and $p_2=(i_2,j_2)$ is defined as

Your task is to calculate, for every pixel, the Manhattan distance to the nearest white pixel and output the resulting distances in the form of an $n \times m$ grid.

inputFormat

The first line contains two integers $n$ and $m$ separated by a space. Then follow $n$ lines, each containing a string of $m$ characters ('0' or '1'). It is guaranteed that there is at least one '1' in the bitmap.

Format:
Line 1: n m
Next n lines: strings of length m.

outputFormat

Output $n$ lines. Each line contains $m$ integers separated by a space representing the minimum Manhattan distance from the corresponding pixel to a white pixel.

Format:
Each line: d₁ d₂ ... d_m

sample

3 4
0001
0011
0110

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