跳蚤国王的游戏

跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个n行m列的网格上排兵布阵。其中的c个格子中（0<=2c<=nm-3)， 每个格子有一只跳蚤，另有c个格子，每个格子中有一只蛐蛐，剩下的nm-2c个格子 是空的。
我们定义跳蚤国王获胜，当某个时刻，网格中存在连续的k个格子，每个格子中 都是跳蚤。连续的k个格子是指，选定某个格子，选定某个方向（上，右，上左，上 右），从这个格子开始在这个方向上连续的k个格子。同理我们可以定义蛐蛐国王获 胜。
在一开始的网格上，保证不存在一方己经获胜，保证至少有3个空格子。
接下来跳蚤国王和蛐蛐国王轮流行动，跳蚤国王先手。跳蚤国王行动的时候，可 以在网格的任意一个空格子里放一只跳蚤；蛐蛐国王行动的时候，可以在网格的任意 一个空格子里放一只蛐蛐。如果某时刻某一方己经获胜，则游戏结束。
现在跳蚤国王想知道，网格中有多少个空格子，使得跳蚤国王第一步在该格子中 放一只跳蚤之后，可以在一步之内获胜。
跳蚤国王在一步之内获胜的意思是，跳蚤国王己经获胜，或者，不论蛐蛐国王下 一步如何行动，蛐蛐国王都不能获胜，且跳蚤国王在接下来的一步中都存在一种获胜 的方案。
跳蚤国王当然知道怎么做啦！但是他想考考你。

包含多组测试数据。
输入的第一行只有一个整数T，表示数据的组数。保证1<=T<= 100。
接下来依次输入T组数据，每组数据的第一行包含四个整数n,m,k,c。保证 $ 1 <= n, m <= 10^9， 5 <= k <= 10^5 ， 0 <= 2c <= min (nm - 3,2 * 10^5) $。
接下来c行，每行包含两个整数x,y，表示第x行，第y列的格子被一只跳蚤占 据。保证1 <= x <= n,1 <= y <= m;每一组数据当中，同一只跳蚤不会被多次描述。
接下来c行，每行包含两个整数x,y，表示第x行，第y列的格子被一只蛐蛐占 据。保证1 <= x <= n,1 <= y <= m;每一组数据当中，同一只蛐蛐不会被多次描述。
同一行相邻的整数之间由一个空格隔开。
我们记 $\sum $ c为T组输入数据的所有c的总和，保证 $\sum c <= 10^5 $。

对于每一组数据依次输出一行一个整数，表示网格中有多少个格子，使得跳蚤国 王第一步在该格子中放一只跳蚤之后，可以在一步之内获胜。

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

2
3
2
0

2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）