Problem Statement

There is a grid divided into squares, with $H$ rows and $W$ columns. The square in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.

If $A_{i,j}$ is ., there is nothing on $(i,j)$; if it is #, a cubic block is placed on $(i,j)$.

Now, a die is placed on $(s_y,s_x)$ with the $1$ face on top. The die can be rolled in the $4$ directions (up, down, left, and right), but it cannot be rolled onto a square with a block or outside the grid.

Is it possible to roll the die so that it is on $(g_y,g_x)$ with the $1$ face on top? If it is possible, find the minimum number of rolls.

Input

$H\ W$
$s_y\ s_x$
$g_y\ g_x$
$A_{1,1}\ A_{1,2}\ \cdots \ A_{1,W}$
$A_{2,1}\ A_{2,2}\ \cdots \ A_{2,W}$
$\vdots$
$A_{H,1}\ A_{H,2}\ \cdots \ A_{H,W}$

• $2 \leq H,W \leq 1000$
• $1 \leq s_y,g_y \leq H$
• $1 \leq s_x,g_x \leq W$
• $(s_y,s_x) \neq (g_y,g_x)$
• $A_{i,j}$ is either . or #
• $A_{s_y,s_x},\ A_{g_y,g_x}$ are .

Output

If it is impossible to roll the die so that it is on $(g_y,g_x)$ with the $1$ face on top, print -1.

If it is possible, print the minimum number of rolls needed to get the die on $(g_y,g_x)$ with the $1$ face on top.

Print a newline at the end.

Sample

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

6

3 2
1 1
3 2
..
..
..

7

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

-1

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

-1