파리채 자리 세기

고정된 다각형을 정수만큼 평행이동해 직사각형 창 안에 넣으면서, 경계를 포함한 어떤 파리도 건드리지 않는 배치의 수를 센다.

어려움8기하누적 합구현수학아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

노먼은 미국에서 인기 있는 모텔을 운영한다. 어머니는 그 모텔을 호텔로 바꾸라고 요구한다. 호텔과 모텔의 차이는 안에 사는 파리의 수뿐이므로, 노먼은 2016년 크리스마스 선물로 변이 KK개인 다각형 모양 파리채를 받았다.

어머니의 요구를 들어주려고 노먼은 파리 NN마리가 앉아 있는 창문 앞에 섰다. 노먼은 파리 한 마리도 해치지 못하는 성격이라, 파리를 한 마리도 맞히지 않으면서 파리채로 창문을 내려치는 방법이 몇 가지인지 알고 싶다.

창문은 왼쪽 아래 꼭짓점이 좌표계의 원점에 놓인 직사각형이다. 내려친 뒤 파리채의 모든 꼭짓점은 정수 좌표에 놓여야 하고, 파리채는 넓이 전체가 창문 안에 들어와야 한다. 파리가 파리채의 꼭짓점, 변, 내부 중 어디에든 있으면 그 파리는 맞은 것이다. 파리채는 돌릴 수도 뒤집을 수도 없어서 평행이동만 할 수 있다. 파리채의 경계는 스스로 교차하지 않는다.

평행이동한 뒤 파리채의 위치가 다르면 서로 다른 방법으로 센다.

입력

첫째 줄에 창문의 오른쪽 위 꼭짓점 좌표 XpX_p, YpY_p와 창문에 앉은 파리의 수 NN이 주어진다. (1Xp,Yp5001 \le X_p, Y_p \le 500, 0NXp×Yp0 \le N \le X_p \times Y_p)

다음 NN개 줄에는 파리 한 마리의 좌표 XX, YY가 주어진다. (0<X<Xp0 < X < X_p, 0<Y<Yp0 < Y < Y_p)

그다음 줄에 파리채의 꼭짓점 수 KK가 주어진다. (3K100003 \le K \le 10000)

다음 KK개 줄에는 파리채의 ii번째 꼭짓점 좌표 XiX_i, YiY_i가 주어진다. (109Xi,Yi109-10^9 \le X_i, Y_i \le 10^9) 꼭짓점은 변으로 이어지는 순서대로 주어지므로 이웃한 두 꼭짓점은 선분으로 연결되고, 마지막 꼭짓점은 첫 꼭짓점과 연결된다.

출력

파리를 한 마리도 맞히지 않고 파리채로 창문을 내려치는 방법의 수를 출력한다.