该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

迷雾重重的清晨，徐老师独自站在教学楼顶，俯瞰着脚下那片神秘的迷宫。

题目描述

徐老师给出一个 $n \times n$ 的迷宫地图，由空地和障碍物构成。奇妙的是，这个迷宫仿佛连接着另一个世界 —— 它是循环的。向左走出边界，会从右边回来；向上走出边界，会从下方重新出现。徐老师决心探索这座迷宫，看看从起点出发，他能否抵达每一处角落。：

. 表示可以通行的空地； * 表示无法穿越的障碍物。

他从左上角的位置 $(1, 1)$（即第一行第一列）出发，想知道到达每一个位置所需的最短步数。如果某个位置无法抵达，就记为 $-1$。

特别说明：这个迷宫是循环的，你可以从任意边缘走出并从对面边缘进入。例如：

• 从第一行往上走，会进入最后一行；
• 从最后一列向右走，会来到第一列。

请你帮助徐老师，输出从起点出发到每个位置的最短步数。

输入格式

第一行一个整数 $n$ $(1 \le n \le 1000)$，表示迷宫的大小。

接下来 $n$ 行，每行 $n$ 个字符，构成迷宫地图。

• . 表示空地；
• * 表示障碍物。
• 保证起点 $(1,1)$ 是 .。

输出格式

输出$n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数表示从起点 $(1,1)$ 到 $(i,j)$ 的最短距离，若无法到达，则输出 $-1$。

输入输出样例

输入

3
.**
.*.
.**

输出

0 -1 -1
1 -1 2
1 -1 -1