Triple

Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Given the finite multi-set $A$ of $n$ pairs of integers, an another finite multi-set $B$ of $m$ triples of integers, we define the product of $A$ and $B$ as a multi-set

$C =A * B \\
= \{\langle a,c,d\rangle \mid \langle a,b\rangle\in A,~\langle c,d,e\rangle\in B~and~b=e\}$

For each $\langle a,b,c\rangle\in C$, its BETTER set is defined as

$BETTER_C(\langle a,b,c\rangle) = \\
\{ \langle u,v,w\rangle\in C \mid \langle u,v,w\rangle \neq \langle a,b,c\rangle,~u\ge a,~v\ge b,~w\ge c \}$

As a \textbf{multi-set} of triples, we define the TOP subset (as a multi-set as well) of $C$, denoted by $TOP(C)$, as

$TOP(C) = \{ \langle a,b,c\rangle\in C \mid BETTER_C(\langle a,b,c\rangle) = \emptyset \}$

You need to compute the size of $TOP(C)$.

Input

The input contains several test cases. The first line of the input is a single integer $t~(1\le t\le 10)$ which is the number of test case. Then $t$ test cases follow.

Each test case contains three lines. The first line contains two integers $n~(1\le n\le 10^5)$ and $m~(1\le m\le 10^5)$ corresponding to the size of $A$ and $B$ respectively.
The second line contains $2\times n$ nonnegative integers
\[a_1,b_1,a_2,b_2,\cdots,a_n,b_n\]
which describe the multi-set $A$, where $1\le a_i,b_i\le 10^5$.
The third line contains $3\times m$ nonnegative integers
\[c_1,d_1,e_1,c_2,d_2,e_3,\cdots,c_m,d_m,e_m\]
corresponding to the $m$ triples of integers in $B$, where $1\le c_i,d_i\le 10^3$ and $1\le e_i\le 10^5$.

Output

For each test case, you should output the size of set $TOP(C)$.

Sample Input

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

Sample Output

Case #1: 5 Case #2: 12

Hint

wange2014

Source

2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

提交代码