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 <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}

/* Aho Corasick */
   

template <int X /*文字の種類*/ >
class AhoCorasick{
public:
  struct Node{
    char c;          //頂点の文字
    int pre;         //親の頂点番号
    int val;         //重み
    int exist;       //単語が存在するか
    int dep;         //ノードの深さ
    int failEdge;    //パターンマッチに失敗した時に戻るノード
    vector<int> bto; //to[i] != -1?  (to[i]):(posからtoへのパターンマッチに失敗した時に戻るノード)
    vector<int> to;  //次の頂点番号
    Node(){};
    Node(char c,int pre,int val = 0,int exist = 0):
      c(c),pre(pre),val(val),exist(exist), to(X,-1){};
  };
  
  vector<Node> v;          //ノード
  function<int(char)> toI; //文字から数字に変換する関数
  int ok;
  
  AhoCorasick(function<int(char)> toI=[](char ch){return ch-'A';} ,char c = '$'/*根に用いる文字*/)
    :toI(toI),ok(false){v.push_back(Node(c, -1, 0/*!!!!!*/));}

  int size(){return v.size();}
  Node operator [](int i)const {return v[i];}
  
  inline void check(int pos){assert(0 <= pos && pos<size());}
  inline int go(int pos,char c, int flag = 0){check(pos);return flag == 0? v[pos].to[toI(c)]:v[pos].bto[toI(c)];}
  inline int go(const string &s,int pos = 0){
    for(char c:s){
      pos = go(pos,c);
      if(pos == -1) return -1;
    }
    return pos;
  }
  
  inline int back(int pos){check(pos);return v[pos].pre;}
  inline int getVal(int pos){check(pos);return v[pos].val;}
  inline int exist(int pos){check(pos);return v[pos].exist;}
  inline int failEdge(int pos){check(pos);assert(ok);return v[pos].failEdge;}
  inline int failEdge(int pos,char to){check(pos);assert(ok);return v[pos].bto[toI(to)];}
  inline int depth(int pos){check(pos);assert(ok);return v[pos].dep;}
  
  inline void addWord(const string &s,int val = 1){
    ok = false;
    int pos = 0, dep = 0;
    for(char c:s){
      v[pos].dep = dep++;
      if(go(pos,c) != -1){pos = go(pos,c);continue;}
      v.push_back(Node(c,pos));
      pos = v[pos].to[toI(c)] = v.size()-1;
    }
    v[pos].dep = dep;
    v[pos].exist = 1;
    v[pos].val = max(v[pos].val, val);  //min,max,+ 臨機応変に変えて
  }

  void build(){
    ok = 1;
    buildBackEdge();
    nextMatch.resize(size());
    for(int i=1;i<size();i++) nextMatch[i] = failEdge(i);
    nextMatch[0] = -1;
  }
  
  vector<int> nextMatch; //to[i] := ノードiを含めないノードiからみて最も単語長が長くなるノード
  //posから見て単語長が最も長くなるようなノードを返す。(pos自体が単語の場合はposを返す)
  int suffixMatch(int pos){
    if(pos == -1) return -1;
    if(exist(pos)) return pos;
    return nextMatch[pos] = suffixMatch(nextMatch[pos]);
  }
    
  //res[i]にはs[i]からmatchする単語の長さが入っている。
  vector<vector<int> > matchedIdx(const string &s){
    assert(exist(0) == 0); //空文字列が単語として存在する場合、たぶん壊れるので直す必要がある。
    assert(ok);
    int n = s.size();
    vector<vector<int> > res(n);
    
    for(int i=0, pos=0;i<n;i++){
      char ch = s[i];
      pos = go(pos, ch, true);
      int p = suffixMatch(pos);
      while(p != -1 && exist(p)){
	res[ i - depth(p) + 1].push_back(depth(p));
	p = suffixMatch(nextMatch[p]);
      }
    }
    return res;
  }
  
private:
  void buildBackEdge(){
    const int root = 0;
    queue<int> Q;
    Q.push(root);
    v[root].failEdge = root;
    for(int i=0;i<size();i++) v[i].bto = v[i].to;
    for(int i=0;i<X;i++) if(v[root].bto[i] == -1) v[root].bto[i] = root;
    
    while(!Q.empty()){
      int pos = Q.front(); Q.pop();
      
      for(int i=0;i<X;i++){
	int to = v[pos].to[i];
	if(to == -1) continue;
	Q.push(to);
	v[to].failEdge = (pos == root)? root:v[ v[pos].failEdge ].bto[i];
	for(int i=0;i<X;i++) if(v[to].bto[i] == -1) v[to].bto[i] = v[ v[to].failEdge ].bto[i];
      }
    }
  }
};


void check(){
  AhoCorasick <26> aho([](char ch){return ch - 'a';});
  aho.addWord("abcde");
  aho.addWord("bc");
  aho.addWord("bab");
  aho.addWord("d");
  aho.addWord("ab");
  aho.build();
  pr(aho.ok);
  for(int i=0;i<aho.size();i++){
    pr(i, aho[i].c, aho[i].failEdge);
  }

  string s = "abcdefgabab";
  auto Idx = aho.matchedIdx(s);
  for(int i=0;i<(int)s.size();i++) pr(i, s[i], Idx[i]);
  
}

void AOJ_2863(){
  int n;
  cin>>n;
  AhoCorasick <26> aho([](char ch){return ch - 'a';});
  for(int i=0;i<n;i++){
    string s;
    cin>>s;
    aho.addWord(s);
  }
  aho.build();
  string t;
  cin>>t;  
  auto Idx = aho.matchedIdx(t);
  int len = t.size();
  vector<int> dp(len+1, 0);
  dp[0] = 1;
  const int mod = 1e9 + 7;
  for(int i=0;i<len;i++){
    for(int l:Idx[i]){
      dp[i+l] = (dp[i+l] + dp[i])%mod;
    }
  }
  int ans = dp[len];
  cout<<ans<<endl;
}


void AOJ_2212(){
 while(1){
    int h,w;
    cin>>h>>w;
    if(h == 0 && w == 0) return;
    vector<string> mp(h);
    for(int i=0;i<h;i++) cin>>mp[i];

    auto func = [](char ch){
      if(ch == 'U') return 0;
      if(ch == 'R') return 1;
      if(ch == 'D') return 2;
      if(ch == 'L') return 3;
      return -1;
    };
  
    AhoCorasick <4> aho(func);
  
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
      string s;
      cin>>s;
      aho.addWord(s);
    }
    aho.build();
    int sy, sx;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++) if(mp[i][j] == 'S') sy = i, sx = j;

    auto bfs = [&]()->int{
      typedef tuple<int,int,int,string> T;
      queue<T> Q;
      Q.push(T(sy, sx, 0, ""));
      vector<vector<vector<int> > > D(h, vector<vector<int> > (w, vector<int>(aho.size(),-1)));
      D[sy][sx][0] = 0;
    
      string str = "URDL";
      int dy[] = {-1, 0, 1, 0};
      int dx[] = {0, 1, 0, -1};
      while(!Q.empty()){
	int y, x, pos;
	string his;
	tie(y, x, pos, his) = Q.front(); Q.pop();
	int cost = D[y][x][pos];
	if(aho.suffixMatch(pos) != -1) continue;
	if(mp[y][x] == 'G') return cost;


	for(int i=0;i<4;i++){
	  int ny = y + dy[i];
	  int nx = x + dx[i];
	  char dir = str[i];
	  if(ny < 0 || nx < 0 || ny >= h || nx >= w || mp[ny][nx] == '#') continue;
	  int to = aho.go(pos, dir);
	  if(to == -1) to = aho.failEdge(pos, dir);
	  if(D[ny][nx][to] != -1) continue;
	  D[ny][nx][to] = cost+1;
	  Q.push(T(ny, nx, to, his + dir));
	}
      }
      return -1;
    };

    int ans = bfs();
    cout<<ans<<endl;
  }
}


signed main(){
  //check();
  AOJ_2212();
  //AOJ_2863();
  return 0;
}