题目描述

一个迷宫由 $H \times W$ 的方格组成，$H$ 表示垂直方向上的方格数目，$W$ 表示水平方向上的方格数目。

从顶部第 $i$ 行、左侧第 $j$ 列的方格 $(i,j)$，如果 $S_{ij}$ 是 #，则表示墙壁；如果 $S_{ij}$ 是 .，则表示通路。

有一个魔法师位于坐标 $(C_h, C_w)$，他可以执行下面两种类型的移动：

• 移动 A：向上下左右四个方向之一走到当前所在方格的上下左右相邻方格中的通路方格。
• 移动 B：使用魔法将自己传送到以当前所在方格为中心的 $5\times 5$ 区域内的某一个通路方格。

无论是哪种移动方式，魔法师都不能走出迷宫范围。

魔法师至少需要使用几次魔法才能到达坐标 $(D_h, D_w)$？

约束条件

• $1 \leq H, W \leq 10^3$
• $1 \leq C_h, D_h \leq H$
• $1 \leq C_w, D_w \leq W$
• $S_{ij}$ 可以为 # 或者 .。
• $S_{C_h C_w}$ 和 $S_{D_h D_w}$ 均为 .。
• $(C_h, C_w)$ 不等于 $(D_h, D_w)$。

---

输入

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

$H$ $W$ $C_h$ $C_w$ $D_h$ $D_w$ $S_{11} \ldots S_{1W}$ $\vdots$ $S_{H1} \ldots S_{HW}$

输出

输出魔法师需要使用的最小次数。如果不能到达坐标 $(D_h, D_w)$，则输出 -1。

---

示例输入 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

示例输出 1

1

例如，魔法师先走到 $(2,2)$，然后使用魔法传送到 $(4,4)$，只需要使用一次魔法。

注意，魔法师不能斜着走。

---

示例输入 2

4 4
1 4
4 1
.##.
####
####
.##.

示例输出 2

-1

从当前位置无法移动。

---

示例输入 3

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

示例输出 3

0

不需要使用魔法。

---

示例输入 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

示例输出 4

2