ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1976. Game Optimization

Time limit: 2.0 second
Memory limit: 64 MB
‘Is anything not working again?’
‘It works, but too slowly. I must constantly recalculate the distance from the ship to the nearest base to check if we can teleport the ship there. When there are too many bases on the map, it works very slowly.’
‘Is the map discrete?’
‘Yes. The map is an n× m grid made up of square cells. Ships and bases can be located at the centers of the cells only.’
‘Then you can precalculate the distances to the nearest base from the centers of each cell.’
‘That’s true. Let’s try it.’

Input

The first line contains integers n and m (1 ≤ n, m ≤ 1 000), which are the numbers of rows and columns in the grid that makes up the map. Then you are given an n× m matrix consisting of zeros and ones. One means that there is a base at the center of the corresponding cell, and zero means that there is no base at that cell. It is guaranteed that there is at least one base and at least one free cell on the map.

Output

Output n lines with m integers in each line. The j-th number in the i-th line must be equal to the squared distance from the center of the cell (i, j) to the nearest base (1 ≤ in; 1 ≤ jm). The numbers in each line must be separated by a space.

Sample

inputoutput
3 4
1000
0000
0010
0 1 4 5 
1 2 1 2 
4 1 0 1 
Problem Author: Idea by Ilya Bushkov
Problem Source: Ural Sport Programming Championship 2013