問題文

縦 $H$ マス、横 $W$ マスの正方形に区切られたグリッドがあります。 上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

$A_{i,j}$ が.のときは $(i,j)$ には何もないことを表し、#のときは $(i,j)$ に立方体のブロックが置かれていていることを表します。

今 $(s_y,s_x)$ に、サイコロが $1$ の目を上にして置かれています。サイコロは上下左右 $4$ 方向に転がすことが可能ですが、ブロックが置かれているマスやグリッドの外には転がせません。

このとき、 $(g_y,g_x)$ に $1$ の目が上になっている状態にサイコロを転がすことは可能でしょうか？可能ならば転がす最小回数を求めてください。

入力

$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}$ は.か#のいずれか
• $A_{s_y,s_x},\ A_{g_y,g_x}$ は.

出力

$(g_y,g_x)$ に $1$ の目が上になっている状態にサイコロを転がすことが不可能な場合、-1を出力してください。

可能な場合、 $(g_y,g_x)$ に $1$ の目が上になっている状態にサイコロを転がす最小回数を出力してください。

最後に改行してください。

サンプル

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