問題文

$N$ 行 $M$ 列のマス目があります。上から $i$ 行目、左から $j$ 列目にあるマスを $(i,j)$ で表します。 特に、左上のマスは $(1,1)$ であり、右下のマスは $(N,M)$ です。

マス目の状態は 二次元配列 $s$ で表され、$s_{ij}$ が # のときマス $(i,j)$ には障害物があり、. または S または G のとき障害物はありません。

ロボットは $0$ 秒にS のマスから スタートし、 G のマスに出来るだけ短い時間で辿り着こうとします。

しかしロボットは常にどの方向にも動けるというわけではありません。

長さ $K$ の文字列 $d$ が与えられます。毎秒、ロボットは隣接するマスに移動するか、今いるマスにとどまることができます。ただし、$t$ 秒後から $t+1$ 秒後にかけては、$t$ を $K$ で割った余りを $r$ ($0 \leq r \leq K-1$) として、 $d_{r+1}$ の方向にのみ $1$ 秒かけて $1$ マス進むことが出来ます。現在いるマスを $(i,j)$ とした時、$d_{r+1}$ が U の場合は $(i-1,j)$ に、 D の場合は $(i+1,j)$ に、L の場合は $(i,j-1)$ に、 R の場合は $(i,j+1)$ に移動できます。マス目の外に出るような移動や、障害物があるマスへの移動は出来ません。

この条件のもとで S からG のマスに辿り着くまでの最短の時間を求めてください。

制約

• $2 \leq N,M \leq 1000$
• $1 \leq K \leq 100000$
• $s$ は # または . または S または G からなる
• S と G の書かれたマスはそれぞれ $1$ つずつ存在する
• $d$ の長さは $K$
• $d$ は U または D または L または R からなる
• $N,M,K$ は整数である

入力例 1Copy

2 3 5
UDRRL
S..
.#G

出力例 1Copy

7

入力例 2Copy

3 3 5
UDUDD
S..
...
.G.

出力例 2Copy

-1

どのように移動しても $2$ 列目に移動出来ません。

入力例 3Copy

3 3 5
UDLRD
S..
.#.
..G

出力例 3Copy

12