题目描述

Kiana非常喜欢装潢，尤其是喜欢铺地毯，对于地毯她还有自己的讲究：铺一层地毯是不够的，要铺很多很多层才会松软，这样自己就可以放心大胆地在地毯上打滚了。

Kiana的房间可以看作一个长宽分别为\(P\)和\(Q\)的矩形，某一天Kiana买回了\(n\)块新的矩形地毯铺在房间的地上，使得每块地毯的边缘都和房间的边缘平行。Kiana认为一个区域足够松软，当且仅当该区域被至少\(n-1\)块地毯所覆盖。为了方便说明地毯的位置，Kiana在房间内建立了一个坐标系，坐标范围为\((0,0)\)到\((P,Q)\)，现在只需要给出每块地毯左下角和右上角的坐标就能唯一确定这块地毯的位置了。

现在Kiana想知道，自己房间里足够松软的区域总面积有多大。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含一个正整数\(T\)，表示输入数据的组数。

接下来依次输入各组数据，每组数据第一行包含三个正整数\(P,Q\)和\(n\)，分别表示Kiana房间的长宽与购买地毯的数量。

每组数据接下来\(n\)行，第\(i\)行包含四个整数\(a_i,b_i,c_i\)和\(d_i\)，表示第\(i\)块地毯左下角的坐标为\((a_i,b_i)\)，右上角的坐标为\((c_i,d_i)\)。

输出格式

输出共一行，包含一个正整数，表示Kiana房间里足够松软的区域的总面积。

输入输出样例

输入样例#1：

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

输出样例#1：

7

输入样例#2：

carpet2.in

输出样例#2：

carpet2.ans

样例解释

下图按照输入顺序从下到上画出了Kiana房间内的所有地毯：

其中黄色表示第\(1\)块地毯，浅红色表示第\(2\)块地毯，浅蓝色表示第\(3\)块地毯，浅紫色表示第\(4\)块地毯，浅绿色表示第\(5\)块地毯。阴影部分即为被至少\(n-1\)块地毯所覆盖的区域，可以看出其面积为\(7\)。

数据范围

对于\(20\%\)的数据，保证\(1\leq n\leq 1000\)。

对于\(50\%\)的数据，保证\(1\leq n\leq 30000\)。

对于\(100\%\)的数据，保证\(1\leq n\leq 3\times 10^5,1\leq P,Q\leq 10^9,1\leq T\leq 5\)。

上面每一档数据中，各有一组数据保证不存在被\(n\)块地毯覆盖的区域，还有一组数据保证\(P,Q\leq 10^4\)。

声明

由于Cloudflare上传文件大小限制，本题目去除了最后一个测试点，满分90分