题目描述

​大唐的科举考试已经进入到了尾声，经过层层选拔虎头虎脑的虎头怪终于来到了殿试环节争夺前三甲，本次殿试的题目是“走迷宫”。

给你一个由字符组成的迷宫，以及一串行动指令，虎头怪需要亲自在迷宫中根据行动指令来进行移动。

迷宫描述（以下字母组成的矩阵）：

• # 代表墙壁，角色不能穿过
• . (点) 代表通道，角色可以移动
• S 代表起点（唯一）
• E 代表出口（唯一）

移动指令（由一个字符串表示，包含以下字符）：

• U - 向上移动
• D - 向下移动
• L - 向左移动
• R - 向右移动

现在，你需要模拟虎头怪的移动。

输入格式

输入 $n,m,k$ 分别表示行，列，最大撞墙次数($1\leq n,m,k\leq100$)。

接下来输入一个 $n*m$ 的矩阵表示迷宫。

接下来输入一串字符表示移动指令(指令长度小于 $1000$)。

输入保证迷宫边缘一定被 # 所包围。

输出格式

按照从上往下的要求，满足即输出。

1. 如果在执行指令的过程中能够从起点走到出口，输出 Escaped in X steps!（$X$ 为实际移动步数）。
2. 如果执行完所有指令后仍在迷宫内且墙壁次数大于 $k$，输出 Hit wall。
3. 如果执行完所有指令后仍在迷宫内，输出 Finished at (x,y)（$x,y$ 坐标为最终位置）。

5 6 2
######
#S...#
#.##.#
#..#E#
######
UUUUURRRDDD

Escaped in 5 steps!

解释 #1

$5,6,2$ 分别表示地图 $5$ 行 $6$ 列以及最大碰撞次数。

从 $S$ 起点出发按照指令 UUUUURRRDDD 移动，移动位置依次为 $(2,3)->(2,3)->(2,3)->(2,3)->(2,3)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)$ 结束，最后一个 $D$ 指令无需执行，虽然一开始撞墙次数超过 $k$，但是能走到终点。

5 6 2
######
#S...#
#.##.#
#..#E#
######
RRR

Finished at (2,5)

5 6 2
######
#S...#
#.##.#
#..#E#
######
URURUR

Hit wall