Description

You are given an $r \times c$ matrix consisting of lowercase letters. Each cell contains one letter. In this setting:

• The top-left corner has coordinates $(0,0)$.
• The top-right corner has coordinates $(c,0)$.
• The bottom-left corner has coordinates $(0,r)$.
• The bottom-right corner has coordinates $(c,r)$.

Note that these coordinates refer to grid points, while letters are placed inside cells.

You are given a polygon whose vertices lie on some grid points, and whose edges are all parallel to the sides of the matrix. Please determine, after translating this polygon up, down, left, and right, what is the maximum number of different positions such that all letters inside the polygon are the same.

Input Format

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

The next $r$ lines each contain $c$ letters, describing the matrix.

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

The next $V$ lines each contain two integers $x, y$, representing the coordinates of one vertex of the polygon. The vertices are given in clockwise order.

Output Format

Output one integer in a single line, representing the number of translated polygon positions whose interior letters are all the same.

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

4

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

0

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

2

Hint

Constraints

• For $40\%$ of the testdata, $r, c, V \le 20$.
• For $70\%$ of the testdata, $V \le 20$.
• For $100\%$ of the testdata, $1 \le r, c \le 500$, $4 \le V \le 500$, $0 \le x \le c$, $0 \le y \le r$.

Notes

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

Translated by ChatGPT 5