Description

You are given a monochrome bitmap of size $n\ \times m$, which contains at least one white pixel. We use $(i,j)$ to denote the pixel in the $i$-th row and $j$-th column, and define the distance between two points $p_1=(i_1,j_1)$ and $p_2=(i_2,j_2)$ as:

Your task is to read the bitmap and, for each pixel, compute the distance to the nearest white pixel. Output the result.

Input Format

The first line contains two space-separated integers $n$ and $m$, where $1 \le n \le 150$ and $1 \le m \le 150$.

Each of the next $n$ lines contains a string of length $m$ consisting of characters '0' and '1'. In the $i$-th of these lines, if the $j$-th character is '1', then pixel $(i,j)$ is white; otherwise it is black.

Output Format

Output an $n\ \times m$ table of numbers. In this table, the $j$-th number in the $i$-th row is $f(i,j)$, which denotes the distance from pixel $(i,j)$ to its nearest white pixel.

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

Hint

Translated by ChatGPT 5