题目描述

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

输入格式

第一行一个整数 $n$ 。

接下来 $n$ 行，每行 $n$ 个整数。

输出格式

输出一个整数。

样例

3
1 0 1
0 0 0
1 0 1

2

3
1 0 0
0 0 0
0 0 0

4

提示

样例1解释

海洋单元格 $(2, 2)$ 和所有陆地单元格之间的距离都达到最大，最大距离为 $2$。

样例2解释

海洋单元格 $(3, 3)$ 和所有陆地单元格之间的距离都达到最大，最大距离为 $4$。

数据范围

$1 <= n <= 100$