Given a table consisting of N rows and M columns. Each cell of the table contains one of the numbers: 0 or 1. The distance between the cells (x1, y1) and (x2, y2) is the sum |x1-x2|+|y1-y2|. You need to build a table, in the cell (i, j) which will contain the minimum distance between the cell (i, j) of the initial table and the cell in which 1 is written. It is guaranteed that there is at least one 1 in the table.
Input
The first line contains two natural numbers N and M, not exceeding 500. Then there are N lines of M numbers each - elements of the table.
Imprint
It is required to display N lines by M numbers - the elements of the desired table.
Examples
| # |
Input |
Output |
| 1 |
2 3
0 0 1
1 0 0
| 1 1 0
0 1 1 |