Given an n*n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1. The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
Input Format
First line contains an integer n. Each of next n lines contain n numbers containing either 0 or 1.
Output Format
Print a 2d matrix where each box contains distance to its nearest 0.
Constraints
1<= n <= 1000
Example
Input
3 0 0 0 0 1 1 1 1 1
Output
2