Description

Norman has a fly swatter shaped as a given $K$-gon. He wants to know how many ways there are to place the fly swatter so that its vertices lie within the rectangle with vertices $(0,0)$ and $(X_p,Y_p)$, and all vertices are lattice points, while making sure that no fly is harmed.

Here, a lattice point means a point whose $x$-coordinate and $y$-coordinate are both integers.

There are $N$ flies inside this rectangle, and each fly can be treated as a point $(X,Y)$. A fly is harmed if and only if it lies on a vertex, an edge, or in the interior of the fly swatter.

The fly swatter cannot be rotated or flipped.

Input Format

The first line contains three positive integers $X_p,Y_p,N$, with the meanings as above.

The next $N$ lines each contain two positive integers $(X,Y)$, representing the coordinates of the $i$-th fly.

The next line contains a positive integer $K$, denoting the number of vertices of the polygon.

The next $K$ lines each contain two integers $(X_i,Y_i)$, describing the coordinates of the vertices when the first vertex of the fly swatter is at $(X_1,Y_1)$. The vertices are given in order.

Output Format

Output the number of feasible ways to place the fly swatter.

4 5 2
1 3
3 4
4
0 0
2 0
2 2
0 2 

4

5 5 3
1 4
1 3
2 2
3
4 7
6 3
7 6 

3

6 7 2
2 5
4 5
8
1 4
3 3
4 1
5 3
7 4
5 5
4 7
3 5 

1

Hint

Explanation of the Samples

Sample 1 Explanation

The valid positions of the fly swatter are as follows:

There are $4$ ways in total.

Sample 2 Explanation

The valid positions of the fly swatter are as follows:

There are $3$ ways in total.

Sample 3 Explanation

The valid positions of the fly swatter are as follows:

There is $1$ way in total.

Constraints

For $63\%$ of the testdata, $1\le X_p,Y_p\le100$.

For $100\%$ of the testdata, $1\le X_p,Y_p\le500,1\le N\le X_p\times Y_p,3\le K\le10^4,0<X<X_p,0<Y<Y_p,-10^9\le X_i,Y_i\le10^9$.

Notes

Translated from COCI2016-2017 CONTEST #3 T6 Meksikanac。

The explanations for Samples 1 and 2 are unofficial.

Translated by ChatGPT 5