問題文

$H$ 行 $W$ 列のマス目があります。上から $r \ (1 \leq r \leq H)$ 行目、左から $c\ (1 \leq c \leq W)$ 列目にあるマスを $(r, c)$ で表します。

マス目の状態は二次元配列 $S$ で表されます。$S_{r,c}$ が # のときマス $(r, c)$ には障害物があり、. のとき障害物はありません。 マス目の外周は障害物 # で囲まれていることが保証されます。

マス上のうしさんとひかりちゃんはお互いのいる場所の交換をしようとしています。

最初、うしさんはマス $(r_a, c_a)$、ひかりちゃんはマス $(r_b, c_b)$ にいます。$2$ 人は、自分が現在いるマスに辺で隣接している $4$ マスのうち、障害物がなく誰もいないマスにのみ移動できます。 $2$ 人は好きな順番で移動することができますが、$2$ 人が同時に別のマスに移動することはできません。最終的に、うしさんはマス $(r_b, c_b)$、ひかりちゃんはマス $(r_a, c_a)$ にいるようにしたいです。

場所の交換ができるか判定し、できる場合は場所の交換にかかる $2$ 人の移動回数の和の最小値を求めてください。

入力

$H$ $W$ $r_a$ $c_a$ $r_b$ $c_b$
$S_{1,1} S_{1,2} \cdots S_{1,W}$
$S_{2,1} S_{2,2} \cdots S_{2,W}$
$:$
$S_{H,1} S_{H,2} \cdots S_{H,W}$

• $4 \leq H, W \leq 1333$
• $1 \lt r_a, r_b \lt H$
• $1 \lt c_a, c_b \lt W$
• $(r_a, c_a) \neq (r_b, c_b)$
• $S_{r,c}$ $(1 \leq r \leq H, 1 \leq c \leq W)$ は # または .
• $S_{r_a, c_a}, S_{r_b, c_b}$ は .
• マス目の外周 ($1$ 行目, $H$ 行目, $1$ 列目, $W$ 列目) は #
• $H, W, r_a, c_a, r_b, c_b$ は整数

出力

$1$ 行に、場所の交換にかかる $2$ 人の移動回数の和の最小値を出力してください。 ただし、場所の交換ができない場合は $-1$ を出力してください。

サンプル

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

6

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

-1

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

6