题目描述

给定一个 $r\times c$ 的由小写字母组成的矩阵。每一个方格内有一个字母。其中：

• 左上角的坐标为 $(0,0)$；
• 右上角的坐标为 $(c,0)$；
• 左下角的坐标为 $(0,r)$；
• 右下角的坐标为 $(c,r)$。

注意这里的坐标是点，而字母放置在方格内。

给定一个顶点在一些方格的顶点上的多边形，且每条边平行于矩阵的边。请你求出，这个多边形经过上、下、左、右的平移，最多存在多少种情况，使得其内部的字母全部相等？

输入格式

输入第一行两个整数 $r,c$，为矩形的长和宽。

接下来的 $r$ 行，每行 $c$ 个字母，描述这个矩阵。

接下来一行一个整数 $V$，为多边形的顶点数。

接下来的 $V$ 行，每行两个整数 $x,y$，表示这个多边形一个顶点的坐标。顶点坐标按顺时针顺序给出。

输出格式

输出一行一个整数，表示通过平移可以得到的内部字母全部相等的多边形数量。

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

提示

数据规模与约定

• 对于 $40\%$ 的数据，保证 $r,c,V\le 20$；
• 对于 $70\%$ 的数据，保证 $V\le 20$；
• 对于 $100\%$ 的数据，保证 $1\le r,c\le 500$，$4\le v\le 500$，$0\le x\le c$，$0\le y\le r$。

说明

题目译自 COCI2010-2011 CONTEST #3 T6 MONO。