2078 - Maze In Warp

問題

あなたは縦Y横Xのよくわからない迷路に迷い込んでしまいました。この迷路は壁＃と道.とWの10以下の整数$r$で構成されていて$W_r$を踏むと$W_r$$_+$$_1$にワープするギミックが仕組まれていることがあるらしいです。ワープには以下の制約があります。

• ワープするために使った$W_r$とワープした先$W_r$$_+$$_1$は使えなくなる
• 連続でワープ($W_1$から$W_2$,そして$W_3$へワープ）することができない
• $W_r$を踏んだ時に$W_r$$_+$$_1$がないときはワープしない

こんな迷路から脱出しましょう。しかしあなたは極度の面倒臭がりやです。なので最短で迷路を脱出しないと死にます。スタートSからゴールGまで最短で迷路を脱出したときにかかる手数（ワープの回数は手数に含まれない）を出力してください。もし脱出できなかった場合はGiveupと出力してください。

入力

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

$Y X$
$A_1$$_1$ $A_1$$_2$... $A_1$$_X$
$A_2$$_1$ $A_2$$_2$... $A_2$$_X$
.
.
.
$A_Y$$_1$ $A_Y$$_2$... $A_Y$$_X$

1行目に迷路の横幅$X$迷路の縦幅$Y$が与えられる。 2行目から#と.と$W_r$とSとGからなる迷路が与えられる。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $2 \leq X, Y \leq 100$
• $1 \leq r \leq 10$

入出力例

入力例1

5 5
S . . . #
. # # . W 1
# # # # #
. . . . .
W 2 . . . G

出力例1

9

Sから始まりW1まで５手かかりそこからW2までワープしそこからGまで進むと4手かかり合計９手かかります。（Wが来た後の数字によって迷路がずれていますので気をつけてください）

入力例2

5 5
S . . . #
. # # . W 2
# # # # #
. . . . .
W 1 . . . G

出力例2

Giveup

W2からワープする先のW3が存在しないのでW2はワープ出来ずにその結果GまでたどりつけないのでGiveupと出力します。

入力例3

7 4
. S . .
# . #.#
W 1 . . W 2
. # . #
W 3 . . W 4
# . # .
G . . .

出力例3

6