<Submit a solution> [0/100]
Task statistics
Number of users: 253
Number of users with 100 points: 205
Average result: 86.5059

Bitmap

Memory limit: 32 MB

There is given a rectangular bitmap of size . Each pixel of the bitmap is either white or black, but at least one is white. The pixel in -th line and -th column is called the pixel . The distance between two pixels and is defined as:

.

Task

Write a program which:

  • reads the description of the bitmap from standard input,
  • for each pixel, computes the distance to the nearest white pixel,
  • writes the results to the standard output.

Input

In the first line of the standard input there is a pair of integer numbers , separated by a single space, , . In each of the following lines of the input exactly one zero-one word of length , the description of one line of the bitmap, is written. On the -th position in the line , , , is 1 if, and only if the pixel is white.

Output

In the -th line of the standard output, , there should be written integers separated by single spaces, where is the distance from the pixel to the nearest white pixel.

Example

For the input data:

3 4
0001
0011
0110

the correct result is:

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

Task author: Marcin Sawicki.

<Submit a solution> [0/100]