Rainforest Clearing

You have been given a rough map of a rainforest obtained via a GPS system. The map is represented by an n×m grid of characters. Each cell is one of the following:

• .: an empty cell;
• *: an impenetrable obstacle;
• #: an area that needs clearing;
• H: the starting position (this cell is also empty).

You are also given t types of moves. For each i (1≤i≤t) a move is defined by two positive integers \(a_i\) and \(b_i\). If your current position is at row \(x\) and column \(y\), then using the i-th move you can proceed in one of the two opposite directions: either in the direction \((a_i, b_i)\) or in the reverse direction \((-a_i, -b_i)\). Once you choose a move and a direction in a day, you must take a positive number of consecutive steps along that direction. That is, you choose a positive integer \(k\) and move to \((x + k\cdot d_x,\, y + k\cdot d_y)\) where \((d_x,d_y)\) is either \((a_i,b_i)\) or \((-a_i,-b_i)\). However, during these steps:

• You cannot step into any cell containing a * (an obstacle).
• If you enter a cell marked with # (an area that needs clearing), you must stop immediately. In that day you will then clear that cell (and it permanently becomes . for all subsequent days).
• You are allowed to stop at any empty cell along the way if no forced stop occurs.

Initially, only the cell marked with H is reached. Each day you select one move (including its direction) from any of the positions reached at the end of the previous day, and based on the rules above, you can reach new cells. Clearing any encountered # cells is permanent and will affect subsequent moves.

You will be given q queries. The i-th query asks: by the end of day \(d_i\), how many distinct cells (regions) have been reached (directly or indirectly) through some sequence of moves? It is guaranteed that at every step there is at least one valid move.

Note: All formulas are given in LaTeX format. For example, the move offsets are represented as \(\{(a_i, b_i)\}_{i=1}^t\).

inputFormat

The input is given as follows:

 n m
 [next n lines: a string of m characters representing the grid]
 t
 [next t lines: two integers a[i] and b[i]]
 q
 [next q lines: an integer d[i] (the day number)]

\(1 \le n, m \le 1000\) (for example), and the grid will contain exactly one H. The characters in the grid are among {., *, #, H}.

outputFormat

For each query, output a single integer on a separate line: the number of distinct cells that can be reached by the end of day \(d_i\). If \(d_i\) exceeds the number of days needed to reach the maximum possible area, output the number corresponding to that maximum reached region.

sample

4 5
H..*.
.##*.
..*..
...#.
2
1 0
0 1
3
1
2
3

6
12
14