問題文

$H$ 行 $W$ 列のグリッドがあります。

上から $i$ 番目、左から $j$ 番目のマスを マス $(i,j)$ と表記します。

マス $(i,j)$ は $C_{i,j}$ が # のときのみ壁で、 $C_{i,j}$ が.,S,G のとき道です。

高橋くんは最初マス $(S_x,S_y)$ にいます。

現在いるマスを $(x,y)$ として、次の $4$ つの操作から道のマスに移動するものを $1$ つ選んで行うことを何回でもできます。

操作A

• マス $(x+1,y)$ に移動する。

操作B

• マス $(x-1,y)$ に移動する。

操作C

• マス $(x,y+1)$ に移動する。

操作D

• マス $(x,y-1)$ に移動する。

どの操作も素数回ずつ行ってマス $(G_x,G_y)$ に移動する方法はありますか？

存在する場合には最小の操作回数を求めてください。

より厳密には、

• 操作A を行った回数を $A$ とする。
• 操作B を行った回数を $B$ とする。
• 操作C を行った回数を $C$ とする。
• 操作D を行った回数を $D$ とする。

$A,B,C,D$ が全て素数であり、かつその操作後にマス $(G_x,G_y)$ に移動しているような操作列が存在するか判定してください。

存在するならば $A+B+C+D$ として考えられる最小値を求めてください。

制約

• $1 \leq H \le 40$
• $1 \leq W \le 40$
• $1 \le S_x,G_x \le H$
• $1 \le S_y,G_y \le W$
• $(S_x,S_y) \neq (G_x,G_y)$
• $C_{i,j}$ は #,.,S,G のどれか
• $C_{S_x,S_y}=$ S
• $C_{G_x,G_y}=$ G
• $(i,j) \ne (S_x,S_y)$ のとき $C_{i,j} \neq$ S
• $(i,j) \ne (G_x,G_y)$ のとき $C_{i,j} \neq$ G

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$
$S_x$ $S_y$
$G_x$ $G_y$
$C_{1,1} C_{1,2} \cdots C_{1,W}$
$\vdots$
$C_{H,1} C_{H,2} \cdots C_{H,W}$

出力

条件を満たす操作列が存在しないならば -1 を出力せよ。

条件を満たす操作列が存在するならば最小の操作回数を出力せよ。

サンプル

3 3
1 1
3 3
S..
.#.
.#G

16

2 8
1 1
2 8
S.......
.......G

-1