本题没有可用的提交语言。

题目描述

现在是 3002 年，教父“倒霉的卢西亚诺”正计划从“矩形国”博物馆实施一场抢劫。问题在于博物馆的墙壁坚不可摧，门口还有守卫，所以他的手下无法从门进入博物馆。幸运的是，博物馆没有屋顶，人们可以从上方进入。于是他决定使用一件来自数千年前的装置——投石机！借助这个装置，他的手下可以飞起来并降落在博物馆的某个地方，而不被守卫发现。

但另一个问题依然存在，那就是博物馆配备了一把高科技激光枪。这把激光枪是基于一项最新的发现而设计的，即可以让激光束沿着一条折线而不是直线传播。不过激光束从发射点到目标点所经过的距离仍然是最短（可能）的。问题是，如果有人降落在博物馆内激光束能够到达的地方，他就会立刻被消灭。教父再次幸运地发现，在博物馆里有一些墙壁和其他障碍物，激光束无法穿过它们。如果他的手下能够降落在这些墙壁的阴影区域内，他们就安全了，也就是说他们在降落之后不会被激光枪消灭，并且他们可以使用特殊装置来使激光枪失效。由于投石机不是非常精确的装置，教父想知道降落在阴影区域的概率，所以他必须计算出博物馆中阴影区域的总面积。

给定博物馆的布局，你需要编写一个程序来计算阴影区域的总面积。是的！这次你真的必须要做到！

当你从俯视图研究博物馆的布局时，你会发现博物馆可以看作是一个有一些障碍物的矩形。这些障碍物是简单的多边形，其边与矩形的边平行。障碍物的内部不会相互重叠。激光枪位于博物馆的右上角。一道激光束由一些线段组成，每一段线段要么是水平的，要么是垂直的。当激光枪选择目标时，它会智能地确定一条到达目标的可行路径并发射激光。一条可行路径具有以下特点：

• 它仅由水平和垂直的线段组成。
• 它永远不会穿过障碍物，但在某些部分可能会与障碍物的边相切。它在一点处永远不会同时与两个障碍物的边相切。
• 在从激光枪到目标的传播过程中，激光束永远不会从左向右或从下向上移动（方向是相对于从上方看博物馆的视角而言的）。

问题是计算博物馆中阴影区域（不包括障碍物内部）的总面积，在这些区域内激光枪无法射中任何一点。在上面的图中，标有 (x) 的点位于一个阴影区域内（见示例输入）。

输入格式

输入包含多个测试用例。第一行包含一个整数 t（介于 1 和 10 之间），表示测试用例的数量。输入文件的其余部分包含 t 个测试用例。每个测试用例的第一行包含两个正整数，分别是矩形的长和宽。第二行包含一个整数 n，表示博物馆中障碍物的数量（介于 0 和 50 之间）。在这之后，有 n 行，包含了障碍物的数据。每行障碍物数据以一个整数 m 开头，表示障碍物的顶点数量（介于 4 和 50 之间），接着是 2m 个数字，它们是按顺时针顺序列出的顶点的 x 和 y 坐标。输入中的每个坐标都是小于 1,000,000 的正整数。矩形的左上角是坐标原点。

输出格式

输出文件必须恰好包含 t 行。每行包含一个数字，即该测试用例中安全区域的总面积。每个测试用例的输出保证可以存储在一个 32 位整数中。所有测试用例的总执行时间必须小于 1 分钟。

输入数据示例 1

1
12 8
3
8 5 1 11 1 11 5 7 5 7 4 9 4 9 2 5 2
4 0 3 3 3 3 4 0 4
4 1 4 2 4 2 6 1 6

输出数据示例 1

12

题目来源

德黑兰 2000 年竞赛题