Uniform Letter Translations

Given an \(r \times c\) matrix of lowercase letters in which letters are placed inside the cells, consider the grid defined by points with coordinates such that the top‐left corner is \((0,0)\) and the bottom–right corner is \((c, r)\). A polygon is given whose vertices lie on some of these grid points and every edge is parallel to the grid edges. The polygon is specified by its vertices in order.

A translation (i.e. a shift in the up, down, left and right directions by an integer offset) is considered valid if the translated polygon lies completely within the grid (i.e. all its vertices remain in the range \([0, c]\) for \(x\) and \([0, r]\) for \(y\)). For each valid translation, consider all cells whose centers \((j+0.5, i+0.5)\) lie strictly inside the translated polygon. We say the translation is good if all these cells contain the same letter. (Note: if the polygon’s interior contains no cells, it is considered to satisfy the condition.)

Your task is to determine the maximum number of valid translations for which the letters contained in the interior are all equal.

Note: The polygon is given with vertices having integer coordinates and its edges are axis‐aligned. The allowed translations are those for which every vertex \((x, y)\) of the polygon translated by \((dx, dy)\) satisfies \(0 \le x+dx \le c\) and \(0 \le y+dy \le r\).

inputFormat

The input begins with two integers \(r\) and \(c\) (the number of rows and columns of the grid).

Then \(r\) lines follow, each containing a string of length \(c\), representing the grid.

The next line contains an integer \(n\), the number of vertices of the polygon.

Then \(n\) lines follow, each containing two integers \(x\) and \(y\), representing the coordinates of a vertex of the polygon in order.

The grid coordinates follow the convention: the top‐left corner is \((0,0)\) and the bottom–right corner is \((c, r)\).

outputFormat

Output a single integer: the number of valid translations for which all the letters inside the translated polygon are equal.

sample

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

1