问题说明

我们有一个 $N \times N$ 的棋盘。用 $(i, j)$ 表示该棋盘上第 $i$ 行从上往下数、第 $j$ 列从左往右数的方格。
棋盘由 $N$ 个字符串 $S_i$ 描述。
字符串 $S_i$ 的第 $j$ 个字符 $S_{i,j}$ 代表了如下内容。

• 如果 $S_{i,j}=$ .，方格 $(i, j)$ 为空白。
• 如果 $S_{i,j}=$ #，方格 $(i, j)$ 被一个不可以移动或移除的白色卒子占据。

我们把一个白色主教放在方格 $(A_x, A_y)$ 上。
根据国际象棋的规则（见注释），找到将这个主教从 $(A_x, A_y)$ 移动到 $(B_x, B_y)$ 所需的最小步数。
如果无法移动到 $(B_x, B_y)$，则报告 -1。

注释

一个位于方格 $(i, j)$ 上的白色主教可以在一步之内到达以下位置。

• 对于每个正整数 $d$，它可以到达 $(i+d,j+d)$，当且仅当满足以下条件：

  • 方格 $(i+d,j+d)$ 存在于棋盘中。
  • 对于每个小于等于 $d$ 的正整数 $l$，$(i+l,j+l)$ 没有被一个白色卒子占据。

• 对于每个正整数 $d$，它可以到达 $(i+d,j-d)$，当且仅当满足以下条件：

  • 方格 $(i+d,j-d)$ 存在于棋盘中。
  • 对于每个小于等于 $d$ 的正整数 $l$，$(i+l,j-l)$ 没有被一个白色卒子占据。

• 对于每个正整数 $d$，它可以到达 $(i-d,j+d)$，当且仅当满足以下条件：

  • 方格 $(i-d,j+d)$ 存在于棋盘中。
  • 对于每个小于等于 $d$ 的正整数 $l$，$(i-l,j+l)$ 没有被一个白色卒子占据。

• 对于每个正整数 $d$，它可以到达 $(i-d,j-d)$，当且仅当满足以下条件：

  • 方格 $(i-d,j-d)$ 存在于棋盘中。
  • 对于每个小于等于 $d$ 的正整数 $l$，$(i-l,j-l)$ 没有被一个白色卒子占据。

约束条件

• $2 \le N \le 1500$
• $1 \le A_x,A_y \le N$
• $1 \le B_x,B_y \le N$
• $(A_x,A_y) \neq (B_x,B_y)$
• $S_i$ 是一个长度为 $N$ 的字符串，由 . 和 # 组成。
• $S_{A_x,A_y}=$ .
• $S_{B_x,B_y}=$ .

输入

输入以以下格式从标准输入中给出：

$N$ $A_x$ $A_y$ $B_x$ $B_y$ $S_1$ $S_2$ $\vdots$ $S_N$

输出

输出答案。

示例输入 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

示例输出 1

3

我们可以按照以下方式将主教从 $(1,3)$ 移动到 $(3,5)$，需要三步，不能减少到两步或更少的步数。

• $(1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)$

示例输入 2

4
3 2
4 2
....
....
....
....

示例输出 2

-1

无法从 $(3,2)$ 移动主教到 $(4,2)$。

示例输入 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

示例输出 3

9