Problem Description

Given a matrix of size $r \times c$ composed of lowercase letters. Each cell contains a letter. The coordinates are defined as follows:
- The top-left corner is $(0,0)$;
- The top-right corner is $(c,0)$;
- The bottom-left corner is $(0,r)$;
- The bottom-right corner is $(c,r)$.

Note that the coordinates refer to points, while the letters are placed within the cells.

Given a polygon whose vertices are at the vertices of some cells and whose edges are parallel to the edges of the matrix, calculate the maximum number of distinct positions the polygon can be translated to such that all the letters inside it are identical.

Input Format

The first line contains two integers $r$ and $c$, representing the height and width of the rectangle.

The next $r$ lines, each containing $c$ letters, describe the matrix.

The next line contains an integer $V$, representing the number of vertices of the polygon.

The next $V$ lines, each containing two integers $x$ and $y$, represent the coordinates of the vertices of the polygon in clockwise order.

Output Format

Output a single integer representing the number of distinct translated positions of the polygon where all the letters inside it are identical.

Sample Input and Output

Sample Input #1

3 3
aaa
aaa
aaa
4
2 0
2 2
0 2
0 0

Sample Output #1

4

Sample Input #2

3 3
aaa
aba
aaa
4
2 0
2 2
0 2
0 0

Sample Output #2

0

Sample Input #3

5 4
xyyx
xyyy
xxyy
xxxx
xxxx
8
1 3
1 2
0 2
0 0
2 0
2 1
3 1
3 3

Sample Output #3

2

Notes

Data Size and Constraints

• For $40\%$ of the test cases, $r, c, V \leq 20$;
• For $70\%$ of the test cases, $V \leq 20$;
• For $100\%$ of the test cases, $1 \leq r, c \leq 500$, $4 \leq V \leq 500$, $0 \leq x \leq c$, $0 \leq y \leq r$.

Notes

This problem is translated from COCI2010-2011 CONTEST #3 T6 MONO.

见题面 Input 部分

见题面 Output 部分