空间折叠

在古老的星尘遗迹中，地面被划分为 H 行 W 列的石板网格。

每块石板要么是完好的（用 . 表示），要么是破碎的（用 # 表示），只有完好石板才能安全站立。

你从入口 (C_h, C_w) 出发，要前往祭坛 (D_h, D_w)。

入口和祭坛保证是完好石板，且位置不同。

你可以执行以下两种行动：

步行：向上、下、左、右移动到相邻的完好石板。该行动不消耗能量。

空间折叠：以当前石板为中心，向 5×5 的方形区域（即行偏移 -2 到 +2，列偏移 -2 到 +2）内的任意完好石板瞬间传送。该行动消耗 1 点能量，且不能超出遗迹边界。

请你计算从入口到祭坛所需的最少能量消耗。如果无法到达，输出 -1。

输入格式

第一行，两个整数 H W。

第二行，两个整数 C_h C_w。

第三行，两个整数 D_h D_w。

接下来 H 行，每行一个长度为 W 的字符串，第 i 行表示迷宫的第 i 行，其中 . 表示道路，# 表示墙壁。

输出格式

输出一个整数，表示最少能量消耗次数。若无法到达，输出 -1。

输入样例1

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

输出样例1

1

输入样例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

说明提示

1 ≤ H, W ≤ 10^3

1 ≤ C_h, D_h ≤ H

1 ≤ C_w, D_w ≤ W

S_ij 为 # 或 .

起点 (C_h, C_w) 和终点 (D_h, D_w) 均为道路。

起点与终点不同。

限制

时间限制：1000ms，内存限制：256MiB