縦 $H$ マス、横 $W$ マスの盤面があります。
上から $i$ 行目、左から $j$ 列目のマスを マス $(i, j)$ と呼びます。
マス $(i, j)$ の状態は文字 $S_{i,j}$ によって以下のように表されます。

• #: 壁
• .: 道
• S: スタートマス
• G: ゴールマス

あなたの目的は、盤面内のロボットをスタートマスからゴールマスに移動させることです。

ロボットは 右、下、左、上 のいずれかの 向き を持っています。
最初、ロボットはスタートマスにいて、 向き は 右 です。

あなたはロボットに以下の 移動命令 を繰り返し出すことができます。
移動命令 ： $1$ 以上の整数 $k$ を $1$ つ指定する。ロボットは現在の 向き に $k$ マス直進し、そのマスで停止する。その後、ロボットの 向き は時計回りに $90$ 度回転する。

ただし、移動の軌跡上や移動先に壁があったり、盤面の外に出たりするような $k$ を指定することはできません。指定できる $k$ が存在しないとき、それ以上 移動命令 を出すことはできません。

ここで、ロボットがマス $(i, j)$ にいるときの移動先は、具体的には次のように表されます。

• 向き が 右 のときに $k$ マス直進する場合、移動先はマス $(i, j+k)$ 。
• 向き が 下 のときに $k$ マス直進する場合、移動先はマス $(i+k, j)$ 。
• 向き が 左 のときに $k$ マス直進する場合、移動先はマス $(i, j-k)$ 。
• 向き が 上 のときに $k$ マス直進する場合、移動先はマス $(i-k, j)$ 。

また、 向き が時計回りに $90$ 度回転すると、具体的には次のように変化します。

• 現在の 向き が 右 ならば、 下 となる。
• 現在の 向き が 下 ならば、 左 となる。
• 現在の 向き が 左 ならば、 上 となる。
• 現在の 向き が 上 ならば、 右 となる。

ロボットをゴールマスに移動させるまでに指定した $k$ の総和を 総移動マス数 と定義します。
総移動マス数 の最小値を求めてください。
ゴールマスに停止させることが不可能な場合はそれを報告してください。

• $ 1 \leq H \leq 1000 $
• $ 1 \leq W \leq 1000 $
• $ H, W $ は整数である。
• $S_{i,j}$ は .、#、S、G のいずれかである。
• スタートマスとゴールマスはちょうど一つずつ存在する。

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

答えを標準出力に $1$ 行で出力してください。
ロボットをゴールマスに停止させることが不可能な場合は -1 を出力してください。