Problem: Background

Mr. A and Mr. B are enthusiastic about the game "Changing Grids". This game is for two players, with player 1 forming the stage and player 2 challenging the stage and aiming for the goal.

Now, A and B have played this game several times, but B has never won because of A's winning streak. So you decided to give B some tips on how to capture this game.

Problem

The state of the two-dimensional grid with the size of vertical H × horizontal W at time T0 = 0 is given as Area 0. Next, the state of this grid switches to the state Areai at time Ti. This switching process is repeated N times. The initial grid is given a start position'S'and a goal position'G'. If you can reach the goal on any grid, output the minimum number of steps at that time, and if you cannot reach the goal, output'-1'. The following conditions must also be met.


* Areai consists of the following elements.
* ‘.’ Is a movable mass without anything
* ‘#’ Is an obstacle and cannot be moved.
*'S' is the square that represents the start position
*'G' is a square that represents the goal position
* It takes 1 second for the player to move to or stay in the current square, either up, down, left, or right adjacent to the current square. However, it cannot move outside the range of obstacle squares or grids.
* The number of steps increases by 1 when you move 1 square from the square where the player is currently to the squares up, down, left, and right. It does not increase if you stay on the spot.
* The size of all grids is vertical H x horizontal W.
* 1 When the grid is switched after moving or staying in place, it is possible to move regardless of the current grid state as long as there are no obstacles in the next grid.
* In all grids, if the goal position given to the initial grid is reached, it is considered as a goal.

Constraints

The input satisfies the following conditions.

* 2 ≤ H, W ≤ 20
* 1 ≤ N ≤ 15
* 1 ≤ Ti ≤ 200 (T1 <T2 <... <TN)
* There is only one start position'S'and one goal position'G' in the initial 2D grid.

Input

The input is given in the following format.


H W
Area0
N
T1
Area1
T2
Area2
..
..
TN
AreaN


Two integers H and W are given on the first line, separated by blanks. This represents the vertical and horizontal dimensions of the two-dimensional grid, respectively. The initial state of the two-dimensional grid is given to each line from the second line to the H + 1 line. The integer N is given on the second line of H +. This represents the number of changes in the 2D grid. The time Ti and the state of switching of N 2D grids are given after the 3rd line of H +. However, Ti is all integers.

Output

Output the minimum number of steps to reach the goal from the start. However, if you cannot reach the goal, output'-1'.

Examples

Input

2 2
S.
.G
1
3
##
##


Output

2


Input

2 2
S.
.G
1
3


Output

2


Input

2 2
S.
.G
1
2


Output

-1


Input

2 3
S##
G
4
2

.##
3

.#
5

.
7


Output

3


Input

4 3
S..
...
.G.
...
4
2

.#

.#
4

..
..

6

.#

..
8

..
..


Output

3


Input

3 3
S##

G
1
1
...
...
...


Output

4

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>

using namespace std;

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
template <typename T> void print_container(ostream& os, const T& c) { const char* _s = " "; if (!c.empty()) { __typeof__(c.begin()) last = --c.end(); foreach (it, c) { os << *it; if (it != last) os << _s; } } }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template <typename T> void print(T a, int n, const string& split = " ") { for (int i = 0; i < n; i++) { cout << a[i]; if (i + 1 != n) cout << split; } cout << endl; }
template <typename T> void print2d(T a, int w, int h, int width = -1, int br = 0) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
template <typename T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
#define dump(v) (cerr << #v << ": " << v << endl)

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define mp(a, b) make_pair(a, b)
#define ten(n) ((long long)(1e##n))

template <typename T, typename U> void upmin(T& a, const U& b) { a = min<T>(a, b); }
template <typename T, typename U> void upmax(T& a, const U& b) { a = max<T>(a, b); }
template <typename T> void uniq(T& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

typedef long long ll;
typedef pair<int, int> pint;

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



int main()
{
    int h, w;
    cin >> h >> w;
    char c[36][36];
    rep(y, h)
        cin >> c[y];

    int n;
    cin >> n;
    int next_t;
    cin >> next_t;

    int sx = -1, sy, gx = -1, gy;
    rep(y, h) rep(x, w)
    {
        if (c[y][x] == 'S')
        {
            sx = x, sy = y;
            c[y][x] = '.';
        }
        else if (c[y][x] == 'G')
        {
            gx = x, gy = y;
            c[y][x] = '.';
        }
    }
    assert(sx != -1 && gx != -1);

    const int inf = ten(8);
    int dp[36][36];
    rep(y, h) rep(x, w)
        dp[y][x] = inf;
    dp[sy][sx] = 0;
    int stage = 0;
    int res = inf;
    rep(cur_t, ten(4))
    {
        if (stage < n && cur_t == next_t)
        {
            rep(y, h)
                cin >> c[y];
            cin >> next_t;
            ++stage;
        }

        int ndp[36][36];
        rep(y, h) rep(x, w)
        {
            ndp[y][x] = inf;
            if (c[y][x] == '#')
                dp[y][x] = inf;
        }
        if (dp[gy][gx] != inf)
            upmin(res, dp[gy][gx]);

        rep(y, h) rep(x, w)
        {
            if (dp[y][x] != inf)
            {
                upmin(ndp[y][x], dp[y][x]);
                rep(dir, 4)
                {
                    int nx = x + dx[dir], ny = y + dy[dir];
                    if (in_rect(nx, ny, w, h))
                        upmin(ndp[ny][nx], dp[y][x] + 1);
                }
            }
        }

        bool updated = false;
        rep(y, h) rep(x, w)
        {
            updated |= dp[y][x] != ndp[y][x];
            dp[y][x] = ndp[y][x];
        }
        if (!updated)
            break;
    }

    cout << (res != inf ? res : -1) << endl;
}