Flyswatter placements

Count the integer translations of a fixed polygon that keep it inside an axis-aligned rectangle and avoid all given points, including points on the boundary.

Hard8GeometryPrefix sumImplementationMathNo attempts yetTime limit1sMemory limit256 MB

Problem

Norman runs one of the more popular motels in America, and his mother wants him to turn it into a hotel. The difference between a hotel and a motel is the number of flies living inside, so for Christmas 2016 Norman got a flyswatter shaped like a polygon with KK edges.

To meet his mother's demand, Norman is standing in front of a window with NN flies on it. Norman would not harm a single fly, so he wants to know how many ways he has to hit the window with the flyswatter without harming any fly.

The window is a rectangle whose lower left vertex sits at the origin of the coordinate system. After the blow, every vertex of the flyswatter must lie on integer coordinates, and the whole area of the flyswatter must be inside the window. A fly is harmed if it lies on a vertex of the flyswatter, on an edge, or inside it. The flyswatter cannot be rotated or flipped, so it can only be translated. The boundary of the flyswatter does not cross itself.

Two ways count as different when the flyswatter ends up at a different position.

Input

The first line contains the coordinates XpX_p, YpY_p of the upper right corner of the window and the number of flies NN on the window (1Xp,Yp5001 \le X_p, Y_p \le 500, 0NXp×Yp0 \le N \le X_p \times Y_p).

Each of the next NN lines contains the coordinates XX, YY of one fly (0<X<Xp0 < X < X_p, 0<Y<Yp0 < Y < Y_p).

The next line contains the number of vertices KK of the flyswatter (3K100003 \le K \le 10000).

Each of the next KK lines contains the coordinates XiX_i, YiY_i of the ii-th vertex of the flyswatter (109Xi,Yi109-10^9 \le X_i, Y_i \le 10^9). The vertices are given in the order the edges join them, so neighbouring vertices are connected by a straight line and the last vertex is connected to the first one.

Output

Print how many ways Norman has to hit the window with the flyswatter without harming a single fly.