Catching Eggs

Time limit5sMemory limit256 MB

Summary

Count the homes inside each of m axis-parallel rectangles and print the total over all days per test case.

Level: Medium6 of 10
Topics: Prefix sum, Sorting, Segment tree
Solved: No attempts yet

Problem

You are a president the public likes a great deal. Every time you go on a parade, people throw eggs at you, because you like eggs, and you catch every egg that comes your way.

A person throws one egg whenever that day's parade area covers their home. You are given the home coordinates of $n$ people on a 2D plane. Several people can live in the same house, so the same coordinate can appear more than once.

You have $m$ days left in your term, and the parade area of each day is fixed in advance. The constitution says a parade area is always an axis-parallel rectangle $[\ell, r] \times [b, t]$ . If a home at $(x, y)$ satisfies both $\ell \le x \le r$ and $b \le y \le t$ , then each person living there throws one egg that day.

Compute the total number of eggs you receive over the days left in your term.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 20$ ).

The first line of each test case contains the number of people $n$ ( $0 < n \le 10000$ ) who throw eggs and the number of days left $m$ ( $0 \le m \le 50000$ ), separated by a blank.

Each of the next $n$ lines contains the coordinates $x$ and $y$ ( $0 \le x, y \le 10^5$ ) of one home.

Each of the following $m$ lines contains four integers $\ell$ , $r$ , $b$ , $t$ ( $0 \le \ell \le r \le 10^5$ , $0 \le b \le t \le 10^5$ ) separated by blanks. The four numbers describe the parade area $[\ell, r] \times [b, t]$ of one day.

Output

For each test case, print the total number of eggs you receive on one line.

Examples7

Example 1

Input

Expected output

2
4

Example 2
Input
```
1
1 0
0 0
```
Expected output
```
0
```

Example 3

Input

1
5 3
7 7
7 7
7 7
0 0
100000 100000
0 100000 0 100000
7 7 7 7
8 9 8 9

Expected output

Example 4

Input

1
4 4
0 0
0 100000
100000 0
100000 100000
0 100000 0 100000
0 0 0 0
100000 100000 100000 100000
0 99999 0 99999

Expected output

Example 5

Input

Expected output

Example 6

Input

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

Expected output

1
0
6

Example 7

Input

1
3 3
10 10
20 20
30 30
0 9 0 9
11 19 0 100000
0 100000 31 100000

Expected output