박물관 강도: 그림자 영역의 넓이

서기 3002년, 악명 높은 대부 불운의 루치아노가 렉틸리니아 박물관을 털 계획을 세운다. 박물관의 벽은 뚫을 수 없고 모든 문은 경비가 지키고 있어 부하들이 옆으로는 들어갈 수 없다. 다행히 이 박물관에는 지붕이 없어 위에서 안으로 떨어질 수 있다. 그래서 대부는 아주 오래된 장치인 투석기를 이용해 부하들을 벽 너머로 날려, 경비를 거치지 않고 박물관 내부 어딘가에 착지시키기로 한다.

하지만 문제가 하나 남아 있다. 박물관을 지키는 첨단 레이저 총이다. 이 총은 빔을 직선이 아니라 직교(축에 평행한) 경로를 따라 유도할 수 있으며, 빔은 항상 발사 지점에서 목표까지 가능한 최단 거리를 지난다. 빔이 도달할 수 있는 자리에 착지하면 즉시 파괴된다. 그러나 박물관 안에는 빔이 통과할 수 없는 벽과 장애물이 있어서, 부하들이 그 그림자(어떤 빔도 닿지 못하는 자리)에 착지하면 살아남아 레이저 총을 무력화할 수 있다. 투석기는 정밀하지 않으므로, 대부는 그림자(안전) 영역의 전체 넓이를 알고 싶어 한다.

위에서 내려다보면 박물관은 여러 장애물을 담은 직사각형이다. 각 장애물은 변이 직사각형의 변과 평행한 단순 다각형이며, 서로 다른 장애물의 내부는 겹치지 않는다. 레이저 총은 박물관의 오른쪽 위 모서리에 있다. 빔은 수평·수직 선분들의 연속이다. 총이 목표를 정하면 유효한 경로를 골라 발사한다. 유효한 경로는 다음 조건을 만족한다.

• 수평 선분과 수직 선분으로만 이루어진다.
• 장애물의 내부로 절대 들어가지 않지만, 장애물의 변에 닿으며 지날 수는 있다. 한 점에서 두 장애물의 변에 동시에 닿을 수는 없다.
• 총에서 목표로 가는 동안 빔은 왼쪽에서 오른쪽으로도, 아래에서 위로도 움직이지 않는다(방향은 위에서 내려다본 기준).

장애물의 내부가 아니면서 어떤 빔도 닿을 수 없는 부분, 즉 그림자 영역의 전체 넓이를 구하라. 위 그림에서 (×)로 표시된 점은 그림자 영역에 속한다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$)가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 직사각형의 가로 길이와 세로 길이(각각 $x$축과 $y$축 방향의 크기)를 나타내는 두 양의 정수가 주어진다.
• 둘째 줄에 장애물의 수 $n$ ($0 \le n \le 50$)이 주어진다.
• 이어지는 $n$개의 줄에는 각각 하나의 장애물이 주어진다. 먼저 꼭짓점의 수 $m$ ($4 \le m \le 50$)이 주어지고, 이어서 꼭짓점을 시계 방향으로 나열한 $x$, $y$ 좌표 $2m$개가 주어진다.

모든 좌표는 1,000,000 미만의 음이 아닌 정수이다. 직사각형의 왼쪽 위 모서리가 원점이고, $x$축은 오른쪽, $y$축은 아래쪽을 향한다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 값은 안전한(그림자) 영역의 전체 넓이, 즉 박물관 내부이면서 모든 장애물의 바깥이고 레이저 총이 닿을 수 없는 영역의 넓이이다. 각 답은 32비트 정수 범위에 들어감이 보장된다.