Problem: The jewel, a national treasure of the Kingdom of Pal, was stolen by bandits. As an adventurer, you heard the rumor and headed for the thief's hideout and managed to get the jewels back.

However, when I went to return the jewel to the castle of the Kingdom of Pal, the guard of the castle said, "My king has not completely trusted you yet. I doubt that the jewel is genuine, and I got it back in the first place. It is a lie, and I suspect that he is a member of the thief who is aiming for the king's life. "

You have been challenged by the guards to see if you really can be trusted. The content of the trial is, "Go to the castle's underground warehouse and place the jewel in the designated place. There is a magic circle that reacts when the jewel is genuine. However, do not cause suspicious behavior. Therefore, do not follow the movement pattern that the guards said from the entrance of the underground warehouse to the designated place. "

For example, for the shape and prohibition pattern of the underground warehouse shown in the figure below, the movement pattern as shown in the figure must not be adopted. This is because part of the movement pattern (highlighted in red) is included in the prohibited pattern. (In addition, the second and third movements "↓↓" in this movement pattern are also included in the prohibited pattern)

<image>

On the other hand, a movement pattern as shown in the figure below is allowed because no part of the movement pattern is included in the prohibited pattern.

<image>

As input, the shape of the underground warehouse and the prohibition pattern are given. Find the minimum number of moves required to move from the entrance to the magic circle without taking the ban pattern.

Notes on Test Cases

Multiple datasets are given in the above input format. Create a program that outputs each data set in the above output format.

When n, m is 0, it indicates the end of input.

<!-



Input

The inputs include the shape of the underground warehouse and the prohibition pattern.

The shape of the underground warehouse is represented as follows. First, two integers N and M are given. It means the number of rows and columns of the underground warehouse, respectively. (1 ≤ N, M ≤ 50)

Subsequently, N lines of character strings consisting of M characters are given. The characters included and their meanings are as follows.

Character | Meaning
--- | ---
S | The entrance to the underground warehouse. Only one is always included per underground warehouse.
G | Magic circle. Only one is always included per underground warehouse.
. | Aisle. You can pass (if you don't take the prohibition pattern).
| Wall. You can't go through the wall.

Next, a prohibition pattern is given. The prohibition pattern is expressed as follows. First, one integer P is given. Means the number of prohibited patterns. (0 ≤ P ≤ 10)

Subsequently, a character string meaning a prohibition pattern is given over P lines. The characters included in the prohibited pattern and their meanings are as follows.

Character | Meaning
--- | ---
U | ↑ move.
Move R |->.
D | ↓ movement.
L | <-Move.

The length of the prohibited pattern is 1 or more and 10 or less. One prohibition pattern may be a substring of another prohibition pattern. It may also include the same prohibition pattern.

Output

Output an integer that means the minimum number of moves required. If you can't reach the magic circle, output -1.

Examples

Input

7 6
......
.####.
.####.
...S#.
...##.
...##.
.....G
3
LD
DD
LLL
7 8
S#......
.#.####.
.#.#G.#.
.#.##.#.
.#....#.
.######.
........
8
DDDD
DDDU
UUUU
UUUD
RRRR
RRRL
LLLL
LLLR
3 8
########
S......G
########
2
U
D
6 10
..........
.S........
..........
..........
........G.
..........
0
6 7
.......
...#...
...#.S.
...###.
.G.....
.......
2
LL
DD
0 0


Output

13
60
7
10
-1


Input

7 6
......
.####.
.####.
...S#.
...##.
...##.
.....G
3
LD
DD
LLL


Output

13


Input

7 8
S#......
.#.####.
.#.#G.#.
.#.##.#.
.#....#.
.######.
........
8
DDDD
DDDU
UUUU
UUUD
RRRR
RRRL
LLLL
LLLR


Output

60


Input

3 8

S......G

2
U
D


Output

7


Input

6 10
..........
.S........
..........
..........
........G.
..........
0


Output

10


Input

6 7
.......
...#...
...#.S.
...###.
.G.....
.......
2
LL
DD


Output

-1


Input

7 6
......
.####.
.####.
...S#.
...##.
...##.
.....G
3
LD
DD
LLL
7 8
S#......
.#.####.
.#.#G.#.
.#.##.#.
.#....#.
.######.
........
8
DDDD
DDDU
UUUU
UUUD
RRRR
RRRL
LLLL
LLLR
3 8

S......G

2
U
D
6 10
..........
.S........
..........
..........
........G.
..........
0
6 7
.......
...#...
...#.S.
...###.
.G.....
.......
2
LL
DD
0 0


Output

13
60
7
10
-1

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <fstream>
#include <cstring>
#include <sstream>

using namespace std;

typedef long long ll;


class Sit{
public:
	int x,y;
	int cur;
};

class AhoCorasick{
private:
  // ノード数の最大サイズ
  static const int MAX_V=10001;
private:
  map<string,int> _dict;
  string idToStr[MAX_V];
  int _vertex;
  // 現在の文字列から次はどの文字列へ遷移できるか
  map<int,set<int> > _stepPrv;
  // // 探索失敗した場合に戻るノード
  // map<int,int> _stepBack;
  int _stepBack[MAX_V];
  // // 辞書文字列の集合
  // set<int> _dictStr;
  bool _dictStr[MAX_V];
  // 点に情報を付加したい時のみ使用
  //T _vertexInfos[MAX_V];
public:
  //AhoCorasick();
  AhoCorasick(const vector<string> inStrings):_vertex(1){
    memset(_dictStr,0,sizeof(_dictStr));
    memset(_stepBack,0,sizeof(_stepBack));
    for(int i=0;i<(int)inStrings.size();i++){
      if(_dict.find(inStrings[i])==_dict.end()){
	idToStr[_vertex]=inStrings[i];
	_dict[inStrings[i]]=_vertex++;
	_dictStr[_vertex-1]=true;
	//_dictStr.insert(_vertex-1);
      }
    }
    makeTree(inStrings);
  }
  int getStrId(string s){
    if(_dict.find(s)==_dict.end())return -1;
    return _dict[s];
  }
  int getVetex(){
    return _vertex;
  }
  // 現在の文字列を外から与え、１文字ずつ探索(valid)
  bool isMatchOneByOne(char ch,int &cur){
    // 必要であれば、ここでcurがdict内に存在しないかチェック
    /*
     */
    while(1){
      int nxt=cur;
      string nstr=idToStr[nxt];
      nstr+=ch;
      bool isFound=false;
      if(_dict.count(nstr)>0){
	isFound=true;
	nxt=_dict[nstr];
      }
      // もし今の場所から次の場所へ遷移可能ならば
      if(isFound&& _stepPrv.find(cur)!=_stepPrv.end()
	 &&_stepPrv[cur].find(nxt)!=_stepPrv[cur].end()){
	// 今回の場所から戻れる場所で、マッチするものがあるかをチェック
	int tmpStr=nxt;
	while(tmpStr!=0){
	  if(_dictStr[tmpStr]){
	    //if(_dictStr.find(tmpStr)!=_dictStr.end()){
	    cur=tmpStr;
	    return true;
	  }
	  tmpStr=_stepBack[tmpStr];
	}
	cur=nxt;/*これをいれる必要あり？*/
	break;
      }
      // そうでなければ、戻って次のループで再び探索を行う
      else{
	// rootで見つからなければ、終了
	if(cur==0)return false;
	// 現在探索中の文字列はノードに存在しない
	//else if(_stepBack[cur]==-1)cur=0;
	//else if(_stepBack.find(cur)==_stepBack.end())cur=0;
	else{
	  // rootでない場合は、戻って今回の文字をもう一度見る
	  cur=_stepBack[cur];
	}
      }
    }
    // もし辞書内の文字列が見つかればtrue
    return (_dictStr[cur]);
    // if(_dictStr.find(cur)!=_dictStr.end())return true;
    // return false;
  }
private:
  // コピーコンストラクタと、代入演算子は使用禁止にする
  AhoCorasick(const AhoCorasick&ah);
  AhoCorasick &operator=(const AhoCorasick&ah);
private:
  // O(size(_dict)^2+size(_dict)*avg(strSize))
  void makeTree(const vector<string> &inStrings){
    // 0または空文字列がルートノード
    _dict[""]=0;
    idToStr[0]="";
    for(int i=0;i<(int)inStrings.size();i++){
      for(int j=0;j<(int)inStrings[i].size();j++){
	string s=inStrings[i].substr(0,j+1);
	// まだ追加されていないのであれば、追加する
	if(_dict.find(s)==_dict.end()){
	  idToStr[_vertex]=s;
	  _dict[s]=_vertex++;
	}
      }
    }
    // 探索を前に進める方向へエッジを結ぶ
    for(map<string,int>::iterator it=_dict.begin();it!=_dict.end();it++){
      for(map<string,int>::iterator iit=_dict.begin();iit!=_dict.end();iit++){
	if(it==iit)continue;
	// もしiit->firstがsize(it->first)+1文字で構成されるならば、エッジを引く
	if(it->first.size()==iit->first.size()-1
	   &&it->first==iit->first.substr(0,it->first.size())){
	  _stepPrv[it->second].insert(iit->second);
	}
      }
    }
    // 探索を後ろへ進める方向へエッジを結ぶ
    for(map<string,int>::iterator it=_dict.begin();it!=_dict.end();it++){
      if(it->first=="")continue;
      // 現在の文字列から先頭i文字を取り除いたものへ戻れるか順番にチェック
      // 戻れなければルートへ戻る
      bool ok=false;
      for(int i=0;i<(int)it->first.size()-1;i++){
	string s=it->first.substr(i+1);
	if(_dict.find(s)!=_dict.end()){
	  _stepBack[it->second]=_dict[s];
	  ok=true;
	  break;
	}
      }
      // ルートへ戻る
      if(!ok)_stepBack[it->second]=0;
    }
  }
};


int h,w;
int n;
char field[51][51];
string prohibits[20];
int sy,sx,gx,gy;
set<int> used[51][51];

const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};

int bfs(){
	vector<string> vs;
	for(int i=0;i<n;i++)vs.push_back(prohibits[i]);
	AhoCorasick ac(vs);
	Sit init;
	init.x=sx;
	init.y=sy;
	init.cur=0;
	queue<Sit> q[2];
	int cur=0;
	int nxt=1;
	q[cur].push(init);
	used[init.y][init.x].insert(0);
	int cnt=0;
	while(q[cur].size()){
		while(q[cur].size()){
			Sit s=q[cur].front();
			q[cur].pop();
			if(s.y==gy&&s.x==gx)return cnt;
			for(int i=0;i<4;i++){
				int ny=s.y+dy[i];
				int nx=s.x+dx[i];
				if(ny>=0&&nx>=0&&ny<h&&nx<w&&field[ny][nx]=='.'){
					char ch=i+'0';
					Sit nsit;
					nsit.y=ny;nsit.x=nx;
					nsit.cur=s.cur;
					bool b=ac.isMatchOneByOne(ch,nsit.cur);
					// matchしたら、遷移しない
					if(b)continue;
					// nsit.curのノードへすでに達したかどうか
					if(used[ny][nx].find(nsit.cur)==used[ny][nx].end()){
						q[nxt].push(nsit);
						used[ny][nx].insert(nsit.cur);
					}
				}
			}
		}
		cnt++;
		swap(cur,nxt);
	}
	return -1;
}

int main(){

	while(cin>>h>>w&&(h|w)){
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)used[i][j].clear();
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin>>field[i][j];
				if(field[i][j]=='S'){
					sy=i;
					sx=j;
					field[i][j]='.';
				}
				else if(field[i][j]=='G'){
					gy=i;
					gx=j;
					field[i][j]='.';
				}
			}
		}
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>prohibits[i];
			for(int j=0;j<(int)prohibits[i].size();j++){
				if(prohibits[i][j]=='U')prohibits[i][j]='0';
				else if(prohibits[i][j]=='R')prohibits[i][j]='1';
				else if(prohibits[i][j]=='D')prohibits[i][j]='2';
				else if(prohibits[i][j]=='L')prohibits[i][j]='3';
			}
		}
		int res=bfs();
		cout<<res<<endl;
	}
	return 0;
}