Programmable Robot

Recently, Soy Ma is taking part in a robot competition. Yesterday, he bought a new kind of programmable robot. He thinks these robots can solve the problem in the maze.
The maze is made up of H × M girds. Each gird is either an empty cell ‘.’ or a wall cell ‘#’. And Soy Ma’s task is to make a program for the robot which can go from START cell ‘S’ to END cell ‘E’ without going into any wall cell.
The robot can receive three kinds of instructions:
1. ’F’: Go forward exactly one cell;
2. ‘L’: Turn left for 90 degrees;
3. ‘R’: Turn right for 90 degrees.
But the competition committee thought it was so easy to solve the problem for such ACMers like Soy Ma and you. Soon they made some additional rules in the competition:
1. The committee will give an standard program for each maze, and the program consists only ‘L’ and ‘R’ instructions;
2. The competitors should only add ‘F’ instructions into the program;
3. The competitors should not change the amount and the order of the ‘L’, ‘R’ instructions.
For example, if the standard program is “LRR”, then the competitor can add ‘F’ instructions in front of ‘L’ to get “FFLRR”, or add after the end of it getting “LRRFFF”, and also “FFLRRF”, “FLFFRFRF”, “LFFFFRRFFF”, etc., but never “RRFL”, “RRF”, “LRFFRR” nor “LLRF”.
Unfortunately, not all standard programs can be adapted to solve the problem for a given maze, and Soy Ma is worrying about that.
So, as a friend of Soy Ma, you want to help him. Now given the maze and the standard program provided by the committee, can you tell Soy Ma whether he can solve the problem?

There are multiple test cases, process to the end of input.
For each case, the first line contains three integers H, W, N, indicating the height and width of the maze and the length of the standard program (1 ≤ H, W ≤ 1000, 1 ≤ N ≤ 1000000).
The second line contains N characters of ‘L’ and ‘R’ which describes the standard program given by the committee.
Next H lines each contain W characters which describes the maze. A ‘.’ character stands for an empty cell, ‘#’ stands for an wall cell, ‘S’ stands for start cell, ‘E’ stands for end cell. You can assume there is only one ‘S’ character and only one ‘E’ character in each maze.
The robot always faces to the north initially.

For each case, output “Yes” if Soy Ma can solve the problem and output “No” otherwise.

2 2 1
L
E.
.S
2 3 2
RR
E..
..S
3 3 8
LLLLLLLL
E#.
...
##S

Yes
No
Yes

2012 Multi-University Training Contest 8