迷路

给定一个 $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。