問題文

一人の少年が，2次元座標状のマップ上を旅しています．マップは $H$ 行 $W$ 列の文字列 $S$ で与えられ，$S_{i,j}$ が . であれば座標 $(i,j)$ に足場があることを， # であれば座標 $(i,j)$ に足場がないことを表します．すべての $\boldsymbol{1 \leq j \leq W}$ に対し，$\boldsymbol{S_{1,j}=}$ . です．

最初，少年は座標 $(s_x, s_y)$ にいます．少年の目標は，ゴールである座標 $(g_x, g_y)$ に行くことです．ここで，$\boldsymbol{s_x = 1, g_x = H}$ です．

少年は，エネルギー $E$ を持っており，はじめ $E=0$ です．少年は，次のような $2$ 種類の移動方法を用いることで，移動することができます．

• 通常ジャンプ：今いる座標を $(x, y)$ とする．$x' \leq x + 1 + \lfloor \frac{E}{2} \rfloor$ を満たすような $x'$ をひとつ選び， $(x', y - 1)$ または $(x',y + 1)$ に移動する．その後，少年の持つエネルギーは， $E=\max(0, x-x')$ に変化する．この移動は，移動先の座標に足場がある場合に限り行える．
• ブーストジャンプ：今いる座標を $(x, y)$ とする．$x' \leq x + 1 + E$ を満たすような $x'$ をひとつ選び， $(x',y - 1)$ または $(x',y + 1)$ に移動する．その後，少年の持つエネルギーは， $E=\max(0, x-x')$ に変化する．この移動は，移動先の座標に足場がある場合に限り行える．

ただし，$1 \leq i \leq H, 1 \leq j \leq W$ を満たさないような座標 $(i, j)$ への移動を行うことはできません．

ブーストジャンプは難しい上に疲れるので，出来るだけその回数を少なくしたいと思っています．

少年がゴールに到達するのに必要なブーストジャンプの回数の最小値を求めてください．

入力

$H$ $W$
$s_x$ $s_y$ $g_x$ $g_y$
$S_1$
$S_2$
$\vdots$
$S_H$

• $H, W, s_x, g_x, s_y, g_y$ は整数である．
• $2 \leq H, W \leq 2000$
• $s_x = 1$
• $g_x = H$
• $1 \leq s_y, g_y \leq W$
• $S_i (1 \leq i \leq H)$ は # および . からなる長さ $W$ の文字列である．
• $S_{1,j} = $ . $(1 \leq j \leq W)$
• $S_{g_x, g_y} =$ .

出力

少年がゴールにたどり着ける場合，必要な最小のブーストジャンプの回数を出力せよ．たどり着けない場合は -1 を出力せよ．

サンプル

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

1

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

-1

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

3