21643_CuttingRectangles

There are several solid rectangles with their edges paralleled to the coordinate axes on the plane, little Bug draws several segments parallel to the x-axis, and he wants to know the sum of the number of solid rectangles that are cut by these segments. We say that a solid rectangle is cut by a segment if and only if they share at least one point. If a solid rectangle is cut by K segments, it will be calculated K times.

The first line of input will be a positive integer T ≤ 20, T test cases follow.

The first line of each test case will be a positive integer N ≤ 30000, the number of solid rectangles. Then N lines follow, each line contains four non-negative integers: x₁, y₁, x₂, y₂, representing the lower left and upper right coordinates of the solid rectangle. It's guaranteed that x₁ < x₂ and y₁ < y₂. After that there will be a positive integer Q ≤ 30000, which is the number of segments. Then Q lines follow, each line contains four non-negative integers: x₃, y₃, x₄, y₄, representing the coordinates of the two end points of the segment, It's guaranteed that x₃ < x₄ and y₃ = y₄,

All integers given are not greater than 100,000,000.

For each test case, output one integer on one line, the sum of the number of solid rectangles that are cut by these segments.

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

3