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>

template<class Converter, class SuffixInfo, int NODE_NUM = 1000000>
class AhoCorasick {
public:
  using value_structure = typename Converter::value_structure;
  using size_type = std::uint64_t;
  static constexpr size_type num_of_kinds = Converter::num_of_kinds;

  using value_type = typename SuffixInfo::value_type;
  using merged_value_type = typename SuffixInfo::merged_value_type;

  struct Node {
    size_type size, end, len, faillink;
    value_type val;
    merged_value_type suf_info;
    std::array<int, num_of_kinds> ch;
    Node () : size(0), end(0), len(0), val(SuffixInfo::identity()),
              suf_info(SuffixInfo::midentity()), faillink(0) { ch.fill(-1); }
  };

private:
  std::vector<Node> node;

public:
  AhoCorasick() {
    node.reserve(NODE_NUM);
    node.push_back(Node());
  }

  void insert(const value_structure& v, size_type num = 1, value_type val = value_type(), size_type k = 0, size_type idx = 0) {
    node[idx].size += num;
    if (k == v.size()) {
      node[idx].end += num;
      node[idx].val = SuffixInfo::operation(node[idx].val, val);
      return;
    }
    size_type nxt = Converter::convert(v[k]);
    if (node[idx].ch[nxt] == -1) {
      node.push_back(Node());
      node[idx].ch[nxt] = node.size()-1;
      node.back().len = k+1;
    }
    insert(v, num, val, k+1, node[idx].ch[nxt]);
  }

  size_type count_prefix(const value_structure& v, size_type k = 0, size_type idx = 0) {
    if (v.size() == k) return node[idx].size;
    size_type nxt = Converter::convert(v[k]);
    if (node[idx].ch[nxt] == -1) return 0;
    return count_prefix(v, k+1, node[idx].ch[nxt]);
  }

  size_type count(const value_structure& v, size_type k = 0, size_type idx = 0) {
    if (v.size() == k) return node[idx].end;
    size_type nxt = Converter::convert(v[k]);
    if (node[idx].ch[nxt] == -1) return 0;
    return count(v, k+1, node[idx].ch[nxt]);
  }

  template<typename F>
  void query(const value_structure& v, const F& f, size_type k = 0, size_type idx = 0) {
    if (node[idx].size > 0) f(node[idx]);
    if (v.size() == k) return;
    size_type nxt = Converter::convert(v[k]);
    if (node[idx].ch[nxt] == -1) return;
    query(v, f, k+1, node[idx].ch[nxt]);
  }

  size_type proceed(size_type k, size_type c, bool need_convert = 1) {
    if (need_convert) c = Converter::convert(c);
    while (node[k].ch[c] == -1)  k = node[k].faillink;
    return node[k].ch[c];
  }

  void build() {
    std::queue<size_type> que;
    for (int i = 0; i < num_of_kinds; i++) {
      if (node[0].ch[i] == -1) node[0].ch[i] = 0;
      else {
        que.push(node[0].ch[i]);
        SuffixInfo::merge(node[node[0].ch[i]].suf_info, node[node[0].ch[i]].val);
      }
    }
    while (que.size()) {
      int k = que.front();
      que.pop();
      for (int i = 0; i < num_of_kinds; i++) {
        if (node[k].ch[i] == -1) continue;
        size_type nx = node[k].ch[i];
        node[nx].faillink = proceed(node[k].faillink, i, false);

        SuffixInfo::merge(node[nx].suf_info, node[nx].val);
        SuffixInfo::merge(node[nx].suf_info, node[node[nx].faillink].suf_info);
        que.push(nx);
      }
    }
  }

  const Node& operator[](size_type k) {
    return node[k];
  }
};

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

class Converter {
public:
  using value_structure = std::string;
  using value_type = typename value_structure::value_type;
  static constexpr std::size_t num_of_kinds = 4;
  static std::size_t convert(const value_type& v) {
    switch (v) {
      case 'U': return 0;
      case 'D': return 1;
      case 'L': return 2;
      case 'R': return 3;
    }
  }
};

class SuffixInfo {
public:
  using value_type = int;
  using merged_value_type = int;
  static value_type identity() { return 0; }
  static merged_value_type midentity() { return 0; }
  static value_type operation(const value_type& a, const value_type& b) {
    return a | b;
  }
  static void merge(merged_value_type& a, const merged_value_type& b) {
    a |= b;
  }
//  static void merge(merged_value_type& a, const value_type& b) {
//    a |= b;
//  }
};

void solve() {
  using namespace std;
  AhoCorasick<Converter, SuffixInfo> ah;
  int n, m;
  cin >> n >> m;
  if (n + m == 0) exit(0);
  vector<string> f(n);
  string dir="UDLR";
  pair<int, int> st, goal;
  for (int i = 0; i < n; i++) {
    cin >> f[i];
    for (int j = 0; j < m; j++) {
      if (f[i][j] == 'S') st = {i, j};
      if (f[i][j] == 'G') goal = {i, j};
    }
  }
  auto in = [&](int y, int x) {
    return 0<=y&&y<n&&0<=x&&x<m&&f[y][x]!='#';
  };
  int P;
  cin >> P;
  for (int i = 0; i < P; i++) {
    string s;
    cin >> s;
    ah.insert(s, 1, 1);
  }
  ah.build();
  using T = tuple<int, int, int, int>; // d, y, x, v
  vector<vector<vector<int>>> d(n, vector<vector<int>>(m, vector<int>(110, (int)1e9)));
  queue<T> que;
  que.emplace(0, st.first, st.second, 0);
  d[st.first][st.second][0] = 0;
  while (que.size()) {
    int dd, ny, nx, v;
    tie(dd, ny, nx, v) = que.front(); que.pop();
    for (int i = 0; i < 4; i++) {
      int yy = ny+dy[i], xx = nx+dx[i], vv = ah.proceed(v, dir[i]);
      if (!in(yy, xx)) continue;
      if (ah[vv].suf_info) {
        continue;
      } else {
        if (d[yy][xx][vv] > dd + 1) {
          d[yy][xx][vv] = dd + 1;
          que.emplace(dd+1, yy, xx, vv);
        }
      }
    }
  }
  int res = 1e9;
  for (int i = 0; i < 110; i++) {
    res = min(res, d[goal.first][goal.second][i]);
  }
  if (res == 1e9) {
    cout << -1 << endl;
  } else {
    cout << res << endl;
  }
}

int main(void) {
  while(1) {
    solve();
  }
}

/*
verify: https://tenka1-2016-final-open.contest.atcoder.jp/submissions/8400970

template<class Converter, class SuffixInfo>
class AhoCorasick

Converter:
	- 要求
		- value_structure: std::string, std::vectorなどの列構造
			- size, operator[] が必要

		- static constexpr std::size_t num_of_kinds
			- 現れる値の種類数

		- static convert(value_type) -> size_t
			- 値を[0, num_of_kinds)に変換する

SuffixInfo:
  - 要求
    - value_type: それぞれの文字列が持つ値の型

    - merged_value_type: suffixが一致する要素の情報をまとめたもの

    - identity -> value_type
      - value_typeの単位元（初期値）

    - midentity -> merged_value_type
      - merged_value_typeの初期値（単位元とは？？？）

    - operation(const value_type&, const value_type&)

    - merge(merged_value_type&, const value_type&)
    - merge(merged_value_type&, const merged_value_type&)


AhoCorasick
	- 提供
		- Node
			- size
				- 部分木に単語がいくつあるか

			- end
				- その頂点で終わる単語がいくつあるか

			- len
				- その頂点までで何文字あるか
			
			- ch[num_of_kinds]
				- それぞれの子のpoolでのindex(存在しなければ-1)

		- insert(value_structure v, num, k)
			- O(|v|)
			- num個のv[k..)を挿入する

		- count_prefix(value_structure v, k)
			- O(|v|)
			- v[k..)をprefixとして含むものがいくつあるか返す

		- count(value_structure v, k)
			- O(|v|)
			- v[k..)がいくつあるか返す

		- query(value_structure v, F f, k)
			- O(|v|)
			- v[k..)のprefixそれぞれについてf(node)を呼び出す

    - build

    - proceed(k, c)
      - 今いる頂点がkのとき、次の文字がcのときに進む頂点を返す
 */