Problem: A robot in a two-dimensional maze again. The maze has an entrance and an exit this time, though.

Just as in the previous problem, the maze is made up of H × W grid cells, its upper side faces north, and each cell is either empty or wall. Unlike the previous, on the other hand, one of the empty cells is connected to the entrance and another to the exit.

The robot is rather complex - there is some control, but not full. It is associated with a controller that has two buttons, namely forward and turn. The forward button moves the robot forward to the next cell, if possible. The robot can not move into a wall nor outside the maze. The turn button turns the robot as programmed. Here the program is a finite sequence of N commands, each of which is either 'L' (indicating a left turn) or 'R' (a right turn). The first turn follows the first command; the second turn follows the second command; similar for the following turns. The turn button stops working once the commands are exhausted; the forward button still works in such a case though. The robot always turns by 90 degrees at once.

The robot is initially put on the entrance cell, directed to the north. Your mission is to determine whether it can reach the exit cell if controlled properly.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.

H W N
s1 ... sN
c1,1c1,2...c1,W
...
cH,1cH,2...cH,W


The first line of a dataset contains three integers H, W and N (1 ≤ H, W ≤ 1,000, 1 ≤ N ≤ 1,000,000).

The second line contains a program of N commands.

Each of the following H lines contains exactly W characters. Each of these characters represents a cell of the maze. "." indicates empty, "#" indicates a wall, "S" indicates an entrance, and "G" indicates an exit. There is exactly one entrance cell and one exit cell.

The end of input is indicated by a line with three zeros.

Output

For each dataset, output whether the robot can reach the exit in a line: "Yes" if it can or "No" otherwise (without quotes).

Examples

Input

2 2 1
L
G.
#S
2 2 2
RR
G.
.S
3 3 6
LLLLLL
G#.
...
.#S
0 0 0


Output

Yes
No
Yes


Input

2 2 1
L
G.
S
2 2 2
RR
G.
.S
3 3 6
LLLLLL
G#.
...
.#S
0 0 0


Output

Yes
No
Yes

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 1000000

enum DIR{
	North,
	East,
	South,
	West,
};

struct Info{
	Info(int arg_row,int arg_col,int arg_turn_count,DIR arg_dir){
		row = arg_row;
		col = arg_col;
		turn_count = arg_turn_count;
		dir = arg_dir;
	}
	bool operator<(const struct Info &arg) const{ //向き変更回数の昇順(PQ)
		return turn_count > arg.turn_count;
	}
	int row,col,turn_count;
	DIR dir;
};

int H,W,N;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
int min_cost[1000][1000][4],next_count[NUM+1][4];
char buf[NUM+1],base_map[1000][1001];
DIR dir_array[4] = {North,West,East,South};

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

void func(){

	for(int i = 0; i <= N; i++){
		for(int k = 0; k < 4; k++){
			next_count[i][k] = BIG_NUM;
		}
	}

	DIR dir = North;
	next_count[0][North] = 0;

	scanf("%s",buf);
	for(int i = 0; i < N; i++){
		switch(dir){
		case North:
			if(buf[i] == 'L'){
				dir = West;
			}else{
				dir = East;
			}
			break;
		case East:
			if(buf[i] == 'L'){
				dir = North;
			}else{
				dir = South;
			}
			break;
		case South:
			if(buf[i] == 'L'){
				dir = East;
			}else{
				dir = West;
			}
			break;
		case West:
			if(buf[i] == 'L'){
				dir = South;
			}else{
				dir = North;
			}
			break;
		}
		next_count[i+1][dir] = i+1; //次にdirの方向になるのはi+1回目
	}

	//情報を右→左に伝える
	for(int i = N-1; i >= 0; i--){
		for(int k = 0; k < 4; k++){
			next_count[i][k] = min(next_count[i][k],next_count[i+1][k]);
		}
	}

	int start_row,start_col,goal_row,goal_col;

	for(int row = 0; row < H; row++){
		scanf("%s",base_map[row]);
		for(int col = 0; col < W; col++){
			if(base_map[row][col] == 'S'){
				start_row = row;
				start_col = col;
			}else if(base_map[row][col] == 'G'){
				goal_row = row;
				goal_col = col;
			}
		}
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int i = 0; i < 4; i++)min_cost[row][col][i] = BIG_NUM;
		}
	}

	priority_queue<Info> Q;
	min_cost[start_row][start_col][North] = 0;
	Q.push(Info(start_row,start_col,0,North));

	int adj_row,adj_col,next_turn_count;
	DIR next_dir;

	while(!Q.empty()){

		if(Q.top().row == goal_row && Q.top().col == goal_col){
			printf("Yes\n");
			return;
		}else if(Q.top().turn_count > min_cost[Q.top().row][Q.top().col][Q.top().dir]){
			Q.pop();
		}else{

			for(int i = 0; i < 4; i++){
				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(rangeCheck(adj_row,adj_col) == false || base_map[adj_row][adj_col] == '#')continue;

				next_dir = dir_array[i];

				if(next_dir == Q.top().dir){ //回転不要
					next_turn_count = Q.top().turn_count;
				}else{
					if(Q.top().turn_count >= N)continue; //これ以上回転できない場合

					next_turn_count = next_count[Q.top().turn_count][next_dir];

					if(next_turn_count == BIG_NUM)continue; //今後、next_dirの向きに回転できない場合
				}

				if(min_cost[adj_row][adj_col][next_dir] > next_turn_count){
					min_cost[adj_row][adj_col][next_dir] = next_turn_count;
					Q.push(Info(adj_row,adj_col,next_turn_count,next_dir));
				}
			}

			Q.pop();
		}
	}
	printf("No\n");
}

int main(){

	while(true){
		scanf("%d %d %d",&H,&W,&N);
		if(H == 0 && W == 0 && N == 0)break;

		func();
	}

	return 0;
}