JOI 君的爱好是在大自然中广阔的滑冰场上滑冰。

滑冰场可以用一个南北长 $R$ 格、东西长 $C$ 格的矩形来表示。我们将从北往南数第 $r$ 行、从西往东数第 $c$ 列的格子记作 $(r, c)$。每个格子要么是 JOI 君可以通过的格子，要么是存在冰块而无法通过的格子。此外，滑冰场外围的所有格子都有冰块，因此 JOI 君不会滑出滑冰场。也就是说，格子 $(i, 1), (i, C) (1 \le i \le R)$ 以及 $(1, j), (R, j) (1 \le j \le C)$ 上都有冰块。

JOI 君的滑冰技术不太好。当他在滑冰场上移动时，他会向东、西、南、北四个方向中的一个方向踢一下当前所在的格子，然后一直滑行，直到撞上冰块前的那个格子停下。从踢出格子到停下算作 1 次移动。如果相邻的格子上有冰块，则不能向该方向移动。

有一天，JOI 君在滑冰时发现，当他踢出一个格子时，那个格子上会长出冰块。除了踢出的起点外，滑行过程中经过的格子不会长出冰块。由于在这种状态下继续滑冰非常危险，JOI 君想尽快逃离这个滑冰场。

JOI 君的当前位置是 $(r_1, c_1)$。为了逃离滑冰场，他需要在出口格子 $(r_2, c_2)$ 处停下。请编写一个程序，计算 JOI 君从当前位置开始移动，最终在出口格子停下所需的最少移动次数。根据滑冰场的状态或 JOI 君的当前位置，有时无论 JOI 君如何移动，都无法在出口格子停下。请注意，仅仅在移动途中经过出口格子并不能算作逃离滑冰场。

题目描述

给定滑冰场上的冰块信息、JOI 君的当前位置以及出口格子的位置，判断 JOI 君是否能从当前位置开始移动并在出口格子停下。如果可以，求出所需的最小移动次数。

输入格式

从标准输入读取以下数据：

• 第 1 行包含两个整数 $R, C$，以空格分隔。这表示滑冰场的大小为南北 $R$ 格，东西 $C$ 格。
• 接下来的 $R$ 行，每行包含一个长度为 $C$ 的字符串。每个字符要么是 '.'，要么是 '#'。其中第 $r$ 行 ($1 \le r \le R$) 的从左往右第 $c$ 个字符 ($1 \le c \le C$) 表示滑冰场格子 $(r, c)$ 的初始状态。字符为 '.' 时表示该格子可以通过，字符为 '#' 时表示该格子上有冰块，无法通过。
• 接下来的一行包含两个整数 $r_1, c_1$，以空格分隔。这表示 JOI 君的当前位置为 $(r_1, c_1)$。
• 接下来的一行包含两个整数 $r_2, c_2$，以空格分隔。这表示滑冰场的出口为 $(r_2, c_2)$。

输出格式

在标准输出中，输出一行，表示 JOI 君从当前位置开始移动并在出口格子停下所需的最少移动次数。如果无论如何移动都无法在出口格子停下，则输出 -1。

数据范围

所有输入数据满足以下条件：

• $3 \le R \le 1000$
• $3 \le C \le 1000$
• $1 \le r_1 \le R$
• $1 \le c_1 \le C$
• $1 \le r_2 \le R$
• $1 \le c_2 \le C$
• 滑冰场外围的所有格子都有冰块。即格子 $(i, 1), (i, C) (1 \le i \le R)$ 以及 $(1, j), (R, j) (1 \le j \le C)$ 上都有冰块。
• 格子 $(r_1, c_1)$ 和格子 $(r_2, c_2)$ 上没有冰块。

子任务

子任务 1 [13 点] 满足以下条件： $R \le 10$ $C \le 10$ * 如果 JOI 君能从当前位置开始移动并在出口格子停下，则所需的移动次数在 10 次以内。

子任务 2 [65 点] 满足以下条件： $R \le 200$ $C \le 200$

子任务 3 [22 点] 没有额外限制。

样例

样例 1

输入：

5 5
#####
#...#
#...#
#...#
#####
2 2
3 3

输出：

4

样例 2

输入：

8 6
######
#..#.#
##...#
#....#
#.#..#
#....#
##...#
######
4 3
6 4

输出：

5

样例 3

输入：

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

输出：

-1

样例 4

输入：

3 3
###
#.#
###
2 2
2 2

输出：

0

说明

在样例 4 中，由于 JOI 君的当前位置就是出口格子，因此所需的移动次数为 0 次。