Algorithms and Data Structures

Gradient of an Image

Given a black and white image with height h and width w, you are asked to apply a gradient filter on it. So, instead of black and white pixels, the image should have a gradient based on the distance from the closest white pixel. Initially, all the black pixels are set to 1, while all the white pixels are set to 0. In the resulting image, the black pixels should have a value equal to the distance from the closest white pixel.
The distance is calculated by the number of steps required to get from one cell to another moving in only horizontal or vertical directions.

Input

The first line of the input contains 2 integers h and w (1 ≀ h, w ≀ 500).
The next h lines contain w numbers representing the initial image.

Output

The program should print the resulting image.

Examples

Input
Output
3 4 1 1 1 0 1 1 0 0 1 0 0 1
3 2 1 0 2 1 0 0 1 0 0 1
Hint
Instead of starting BFS from a single cell, you can start BFS from multiple sources.
In literature, this is called multi-source BFS.

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 2.5 MB

To check your solution you need to sign in
Sign in to continue