题目描述

给定有限的整数对的多重集合 $A$ 和另一个有限的整数三元组的多重集合 $B$，我们将 $A$ 和 $B$ 的乘积定义为一个多重集合

$C=A\times B=\{(a,c,d)|(a,b)\in A,(c,d,e)\in B\text{ and } b=e\}$

对于每个 $(a,b,c)\in C$，其更好的集合被定义为

$BETTERC((a,b,c))=\{(u,v,w)\in C|(u,v,w)\ne(a,b,c),u \ge a,v\ge b,w\ge c\}$

作为整数三元组的多重集合，我们将 $C$ 的顶部子集（也是一个多重集合）定义为 $TOP(C)$，表示为

$TOP(C)=\{(a,b,c) \in C|BETTERC((a,b,c))=\phi\}$

你需要计算 $TOP(C)$ 的大小。

输入格式

输入包含多个测试用例。

第一行是一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例包含三行。第一行包含两个整数 $n$ 和 $m$ ，分别对应 $A$ 和 $B$ 的大小。

第二行包含 $2×n$ 个非负整数 $[a_1,b_1,a_2,b_2,\cdots,a_n,b_n]$，描述了多重集合 $A$，其中 $1 \le a_i,b_i \le 10^5$。

第三行包含 $3×m$ 个非负整数 $[c_1,d_1,e_1,c_2,d_2,e_2,\cdots,c_m,d_m,e_m]$，对应于 $m$ 中的整数三元组，其中 $1 \le c_i,d_i \le 10^3$ 和 $1 \le e_i \le 10^5$。

输出格式

对于每个测试用例，你应该输出集合 $TOP(C)$ 的大小。

2
5 9
1 1 2 2 3 3 3 3 4 2
1 4 1 2 2 1 4 1 1 1 3 2 3 2 2 4 1 2 2 4 3 3 2 3 4 1 3
3 4
2 7 2 7 2 7
1 4 7 2 3 7 3 2 7 4 1 7

Case #1: 5
Case #2: 12

样例分析

如上所述。

数据范围与提示

对于 $100\%$ 的数据：$1 \le t \le 10$，$1\le n \le 10^5$, $1 \le m \le 10^5$。