Bitmap

Time limit1sMemory limit128 MB

Summary

For each black pixel in an n by m bitmap, output the Manhattan distance to the closest white pixel.

Level: Medium5 of 10
Topics: BFS, Graph, Dynamic programming
Solved: No attempts yet

Problem

You are given a rectangular bitmap of size $n \times m$ . Each pixel of the bitmap is either white or black, and at least one pixel is white. The pixel in row $i$ and column $j$ is denoted $(i, j)$ .

The distance between two pixels $p_1 = (i_1, j_1)$ and $p_2 = (i_2, j_2)$ is defined as

$d(p_1, p_2) = |i_1 - i_2| + |j_1 - j_2|.$

Write a program that, for every pixel, computes the distance to the nearest white pixel.

Input

The first line contains two integers $n$ and $m$ separated by a single space ( $1 \le n \le 182$ , $1 \le m \le 182$ ).

Each of the following $n$ lines contains one string of length $m$ made of the characters 0 and 1, describing one row of the bitmap. In the string that describes row $i$ of the bitmap, the $j$ -th character is 1 if and only if the pixel $(i, j)$ is white ( $1 \le i \le n$ , $1 \le j \le m$ ).

Output

Print $n$ lines. The $i$ -th line must contain $m$ integers $f(i, 1), \dots, f(i, m)$ separated by single spaces, where $f(i, j)$ is the distance from the pixel $(i, j)$ to the nearest white pixel.

Examples4

Example 1

Input

Expected output

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

Example 2
Input
```
1 1
1
```
Expected output
```
0
```
Example 3
Input
```
1 5
00100
```
Expected output
```
2 1 0 1 2
```
Example 4
Input
```
2 2
11
11
```
Expected output
```
0 0
0 0
```