CF97D.Robot in Basement

The Professor has lost his home robot yet again. After some thinking Professor understood that he had left the robot in the basement.

The basement in Professor's house is represented by a rectangle n × m, split into 1 × 1 squares. Some squares are walls which are impassable; other squares are passable. You can get from any passable square to any other passable square moving through edge-adjacent passable squares. One passable square is the exit from the basement. The robot is placed exactly in one passable square. Also the robot may be placed in the exit square.

Professor is scared of going to the dark basement looking for the robot at night. However, he has a basement plan and the robot's remote control. Using the remote, Professor can send signals to the robot to shift one square left, right, up or down. When the robot receives a signal, it moves in the required direction if the robot's neighboring square in the given direction is passable. Otherwise, the robot stays idle.

Professor wrote a sequence of k commands on a piece of paper. He thinks that the sequence can lead the robot out of the basement, wherever it's initial position might be. Professor programmed another robot to press the required buttons on the remote according to the notes on the piece of paper. Professor was just about to run the program and go to bed, when he had an epiphany.

Executing each command takes some energy and Professor doesn't want to get huge electricity bill at the end of the month. That's why he wants to find in the sequence he has written out the minimal possible prefix that would guarantee to lead the robot out to the exit after the prefix is fulfilled. And that's the problem Professor challenges you with at this late hour.

教授又一次弄丢了自家的机器人。经过一番思考，教授意识到自己把机器人留在了地下室。

教授家的地下室可建模为一个 $n \times m$ 的矩形网格，被划分为若干 $1 \times 1$ 的小方格。其中一些方格是不可通行的墙壁；其余方格是可通行的。任意两个可通行方格之间均存在一条仅由边相邻的可通行方格构成的路径。其中一个可通行方格是地下室的出口。机器人恰好位于某一个可通行方格中（该方格也可能是出口）。

教授害怕在夜晚进入漆黑的地下室寻找机器人。不过，他手中有一份地下室平面图以及机器人的遥控器。借助遥控器，教授可以向机器人发送信号，使其向左、右、上或下移动一格。当机器人接收到信号后，若其在指定方向上的相邻方格是可通行的，则机器人向该方向移动；否则，机器人保持静止。

教授在一张纸上写下了一串长度为 $k$ 的指令序列。他认为：无论机器人初始位置如何，只要执行该序列，就能将其引导至出口。教授已编程另一台机器人，按纸上的记录依次按下遥控器对应按钮。教授正准备运行该程序然后去睡觉，却突然灵光一闪。

每执行一条指令都会消耗一定能量，而教授不想月底收到巨额电费账单。因此，他希望从自己写下的指令序列中，找出最短的前缀——只要执行该前缀，即可保证：无论机器人初始位置如何（只要位于某个可通行方格），执行完该前缀后，机器人必然已到达出口。这便是教授在这个深夜向你提出的挑战。

The first line contains three integers n, m and k (3 ≤ n, m ≤ 150, 1 ≤ k ≤ 105). Next n lines contain m characters each — that is the Professor's basement's description: "#" stands for a wall, "." stands for a passable square and "E" stands for the exit from the basement (this square also is passable). It is possible to get from each passable square to the exit, all squares located by the n × m rectangle's perimeter are the walls. Exactly one square is the exit from the basement. The last line contains k characters, the description of the sequence of commands that Professor has written out on a piece of paper. "L", "R", "U", "D" stand for commands left, right, up and down correspondingly.

第一行包含三个整数 $n$、$m$ 和 $k$（满足 $3 \leq n, m \leq 150$，$1 \leq k \leq 10^5$）。接下来的 $n$ 行，每行包含 $m$ 个字符，描述教授地下室的布局：# 表示一堵墙，. 表示一个可通过的方格，E 表示地下室的出口（该方格同样可通过）。每个可通过的方格均能到达出口；位于 $n \times m$ 矩形边界的全部方格均为墙。地下室有且仅有一个出口。最后一行包含 $k$ 个字符，表示教授写在纸上的指令序列。其中 "L"、"R"、"U"、"D" 分别代表向左、向右、向上、向下移动的指令。

Print in the output file the length of the smallest possible prefix that will lead the robot to the exit square. In other words, wherever the robot had been positioned initially, it should be positioned in the exit square after all the commands from the prefix are fulfilled (during doing commands the robot can come and leave the exit square, but only the last position of the robot is interesting for us). If Professor is mistaken and no prefix (including the whole sequence) can bring the robot to the exit, print "-1" (without the quotes). If there is the only passable square and it is the exit, print "0" (without the quotes).

在输出文件中打印能引导机器人到达出口方格的最短可能前缀的长度。换言之，无论机器人初始位置如何，在执行该前缀中的所有指令后，其最终位置都必须为出口方格（在执行指令过程中，机器人可以多次进入或离开出口方格，但我们只关心其最终位置）。如果教授判断有误，即不存在任何前缀（包括整个指令序列）能使机器人抵达出口，则输出 “-1”（不带引号）。如果地图中仅有唯一一个可通过的方格，且该方格即为出口，则输出 “0”（不带引号）。