Changing Grids

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

inputFormat

outputFormat

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

样例

2 3
S##
G
4
2

.##
3

.#
5

.
7

3