$H \times W$ のマス目があります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ で表します。
各マス目の状態は $H$ 個の文字列 $S_1, S_2, \ldots, S_H$ で表され、$S_{ij}$ が # ならば壁、. ならば道、S ならばスタート、G ならばゴールを表します。
はじめ、S が書かれたマスにロボットが静止しています。このロボットは、$1$ 回の移動において上下左右の方向を選ぶと壁または外周に当たるまで進み続け、その手前で静止します。より厳密には、ロボットが壁以外のマス $(i, j)$ に静止しているとき

• $(i+1, j), (i+2, j), \ldots, (i+k, j)$ がすべて壁以外のマス、かつ $(i+k+1, j)$ が壁かマス目の外であるような非負整数 $k$ に対して $(i+k, j)$ に動かす
• $(i-1, j), (i-2, j), \ldots, (i-k, j)$ がすべて壁以外のマス、かつ $(i-k-1, j)$ が壁かマス目の外であるような非負整数 $k$ に対して $(i-k, j)$ に動かす
• $(i, j+1), (i, j+2), \ldots, (i, j+k)$ がすべて壁以外のマス、かつ $(i, j+k+1)$ が壁かマス目の外であるような非負整数 $k$ に対して $(i, j+k)$ に動かす
• $(i, j-1), (i, j-2), \ldots, (i, j-k)$ がすべて壁以外のマス、かつ $(i, j-k-1)$ が壁かマス目の外であるような非負整数 $k$ に対して $(i, j-k)$ に動かす

のいずれかの操作を行うことができます。ただし、$(i, j)$ がマス目の外であるとは $1 \leq i \leq H, 1 \leq j \leq W$ が満たされないことをいいます。
このとき、ロボットが G のマスに静止している状態にするために最小で何回操作を行う必要があるかを求めてください。

• $H,W$は整数
• $1 \leq H, W \leq 1000$
• $S_i$ は #, ., S, G のみからなる長さ $W$ の文字列
• S および G は入力の中にちょうど $1$ 回ずつ現れる

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

$H\ W$
$S_1$
$S_2$
$\vdots$
$S_H$

ロボットが G のマスに静止している状態にするために必要な操作回数の最小値を $1$ 行に出力せよ。そのようなことが不可能な場合は、代わりに -1 を出力せよ。