Gizem is a highly placed scientist from Middle Earth Technical University, and the inventor of the hopper. However, she didn't have time to test it yet.

Ersel wanted to test Gizem's hoppers on a \(\mathbf{N \times M}\) field to help her. He is going to start from the location \(\mathbf{A}\) and end at the location \(\mathbf{Z}\).

Ersel has \(\mathbf{K}\) available hoppers and he can use them multiple times. Each hopper has a direction \(\mathbf{Dir}\) and distance \(\mathbf{Dis}\). He can use these hoppers to directly hop \(\mathbf{Dis_i}\) units in \(\mathbf{Dir_i}\) direction. The direction can be west, north, east, or south. (\(\mathbf{W, N, E, S}\))

There are also some obstacles on the grid represented with characters *. Note that Ersel can directly jump over those obstacles using the hoppers Gizem invented but can't land on them.

Can you calculate the minimum number of hops for Ersel to reach his destination \(\mathbf{Z}\)?

Input

In the first line, integers \(\mathbf{N}\), \(\mathbf{M}\) are given. Those are the field's dimensions.

In the following \(\mathbf{N}\) lines \(\mathbf{N} \times \mathbf{M}\) field is given. A and Z characters represent the start and endpoints, the * character represents that there is an obstacle on that point, and . means that location is available to hop on.

In the next line, the number of available hoppers, \(\mathbf{K}\) is given.

In the next \(\mathbf{K}\) lines, \(\mathbf{Dir_i}\) and \(\mathbf{Dis_i}\) are given for each of the available hoppers. Those are the distance and the direction the corresponding hopper can jump to.

• \(2 \leq \mathbf{N, M} \leq 200\)
• \(1 \leq \mathbf{K} \leq 250\)
• \(\mathbf{Dir_i} \in \mathbf{\{W, N, E, S\}}\)
• \(1 \leq \mathbf{Dis_i} \leq \mathbf{N}\)

Output

The minimum number of hops Ersel makes to reach the destination point \(\mathbf{Z}\). If there are no ways that Ersel can reach his destination, print -1.

Examples

Input 1:

3 3
**A
**.
Z..
5
W 3
S 1
S 2
W 2
W 5

Output 1:

2

Input 2:

4 4
*A..
*...
Z...
....
5
W 3
S 1
S 2
W 2
W 5

Output 2:

-1

Explanation

Input 1

Ersel can move 2 cells south (using the third hopper) from the starting point at first. Then he can move 2 cells west (using the fourth hopper). He would be in the point Z at the end.

Input 2

For the second input, there is no sequence with the given hoppers to reach the destination point.