AT_mujin_pc_2018_e 迷路

# 迷路 给定一个 $N$ 行 $M$ 列的网格地图。第 $i$ 行，第 $j$ 列的格子可以用 $(i,j)$ 表示。特别地，左上角的格子是 $(1,1)$，右下角的格子是 $(N,M)$。 网格地图的状态由二维数组 $s$ 来表示，当 $s_{i,j}$ 是 `#` 时表示格子 $(i,j)$ 上有障碍物，当 $s_{i,j}$ 是 `.` 或 $S$ 或 $G$ 时表示格子上没有障碍物。 机器人从起点 $S$ 出发，在尽可能短的时间内到达目标 $G$。 然而，机器人并不总是可以朝任意方向移动。 给定一个长度为 $K$ 的字符串 $d$，每秒钟，机器人可以移动到相邻的格子，或者停留在当前格子。但是，从 $t$ 秒到 $t+1$ 秒之间，其中 $t$ 对 $K$ 取余得到余数 $r (0 \le r \le K-1)$，那么机器人只能朝着 $d_{r+1}$ 的方向移动一格，并花费 $1$ 秒钟的时间。假设当前位于 $(i,j)$，若 $d_{r+1}$ 是 $U$，则机器人可以移动到 $(i-1,j)$；若 $d_{r+1}$ 是 $D$，则机器人可以移动到 $(i+1,j)$；若 $d_{r+1}$ 是 $L$，则机器人可以移动到 $(i,j-1)$；若 $d_{r+1}$ 是 $R$，则机器人可以移动到 $(i,j+1)$。机器人不能移动出网格的范围，也不能移动到有障碍物的格子上。 在以上条件下，请求出从起点 $S$ 到目标 $G$ 的最短时间。

输入按以下格式从标准输入给出。 ``` N M K d1...dK s11...s1M ... sN1...sNM ```

输出机器人从 $S$ 移动到 $G$ 所需的最短时间。如果无论如何移动都不能从 $S$ 移动到 $G$，则输出 `-1`。

### 制約 - $ 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 $ は整数である ### Sample Explanation 2 どのように移動しても $ 2 $ 列目に移動出来ません。