The government is planing to build a walkway for tourists in the middle of an oak forest. The forest
can be represented as plane with N special lattice points representing oaks.
The walkway is represented as a rectangle with sides parallel to the axes. If the sides of walkway
rectangle intersect any oak lattice points, such oaks need to be axed down. Oaks inside the rectangle do
not represent problems and need not be cut down.
Ljubo is the state secretary of Forestry and an passionate nature lover, so he ordered the secretary of
Tourism to provide him with a list of P possible rectangle walkways that are attractive enough to draw
in tourists.
Ljubo plans to select the walkway that needs the smallest amount of oak trees to be cut down. Since we
also like trees, would you be so kind and write a program that will determine the number of oaks that
will be cut down for each walkway. Remember only the oaks intersecting the sides of the rectangle
need to be cut.
There are multiple test cases and the input file begins with an integer T indicating the total number of test cases. For each test case, the first line contains one integer N (1 ≤ N ≤ 300000), number of oaks.
The next N lines contain two integers each X and Y (1 ≤ X, Y ≤ 109) coordinates of oaks. There will be at
most one oak on each lattice point.
The next line contains one integer P (1 ≤ P ≤ 100000), number of walkways.
The next P lines contain four integers each X1, Y1, X2 and Y2 (1 ≤ X1 < X2 ≤ 109, 1 ≤ Y1 < Y2 ≤ 109)
coordinates of the lower left (X1, Y1) and upper right (X2, Y2) corner of the rectangle.
For each test case, output P integers, one per line, the number of oaks that need to be cut down for each walkway in the order they are presented in the input. DO NOT output any other empty lines between test cases.
2 6 1 2 3 2 2 3 2 5 4 4 6 3 4 2 2 4 4 2 2 6 5 3 3 5 6 5 1 6 6 6 1 2 3 2 2 3 2 5 4 4 6 3 3 2 2 4 4 2 2 6 5 3 3 5 6
3 4 0 1 3 4 0
Migrated from old NTUJ.
Croatian Olympiad in Informatics 2010
| No. | Testdata Range | Score |
|---|