Problem C: Changing Grids

Background

A君とB君は、『Changing Grids』というゲームに熱中している。このゲームは2人用で、プレイヤー1がステージを構成し、プレイヤー2がそのステージに挑戦しゴールを目指すというものである。

今、A君とB君はこのゲームを何度かプレイしているが、A君の連勝でB君は1度も勝つことができていない。そこであなたは、B君にこのゲームを攻略するためのヒントを教えてあげることにした。

Problem

時刻T0 = 0における縦H×横Wの大きさの二次元グリッドの状態がArea0として与えられる。次に、このグリッドの状態は時刻Tiにおいて、状態Areaiに切り替わる。この切り替わる過程はN回繰り返される。初期状態のグリッドにはスタートの位置'S'とゴールの位置'G'が与えられる。いずれかのグリッドにおいてゴールへ辿り着ける場合は、そのときの最小歩数を出力し、ゴールへ辿り着けない場合は、'-1'を出力せよ。なお、以下の条件も満たす必要がある。

Input

入力は以下の形式で与えられる。

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

1行目に2つの整数H,Wが空白区切りで与えられる。これは、それぞれ二次元グリッドの縦と横の大きさを表す。2行目からH+1行目までの各行に初期状態の二次元グリッドの状態が与えられる。H+2行目に整数Nが与えられる。これは、二次元グリッドの変化する回数を表す。H+3行目以降にN個の二次元グリッドの切り替わる時刻Tiとその状態が与えられる。ただし、Tiは全て整数である。

Constraints

入力は以下の条件を満たす。

Output

スタートからゴールへ到達するための最小の歩数を出力せよ。ただし、ゴールに到達できない場合は'-1'を出力せよ。

Sample Input 1

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

Sample Output 1

2

1番目のグリッドに切り替わる時刻T1は3であり、時間内にプレイヤーはスタートからゴールまでの最短歩数が2歩で辿り着くことが可能なので2を出力する。

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

2 3
S##
##G
4
2
###
.##
3
###
#.#
5
###
##.
7
###
###

Sample Output 3

3

Sample Input 4

4 3
S..
...
.G.
...
4
2
###
#.#
###
#.#
4
###
#..
#..
###
6
###
#.#
###
#..
8
###
#..
#..
###

Sample Output 4

3

Sample Input 5

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

Sample Output 5

4