 Server Time: Tue Jan 21, 2020 12:38 am
 Welcome ( logout ) 1267 - Points in Rectangle (II)  PDF (English) Statistics Forum
 Time Limit: 3 second(s) Memory Limit: 64 MB

As the name says, this problem is about finding the number of points in a rectangle whose sides are parallel to axis. All the points and rectangles consist of 2D Cartesian co-ordinates. A point that lies in the boundary of a rectangle is considered inside.

Initially you are given a list of points, after that you are given some queries, each query contains a rectangle. Your task is to find the number of points that lie in each of the query rectangle.

# Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers: p, q (1 ≤ p, q ≤ 50000), where p denotes the number of points and q denotes the number of query rectangles.

Each of the next p lines contains two integers x y denoting the co-ordinate of a point. All the points are distinct.

Each of the next q lines contains four integers x1 y1 x2 y2 meaning that you are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2). You can assume that (x1 < x2, y1 < y2).

You can assume that the values of the co-ordinates lie between 0 and 109 (inclusive).

# Output

For each case, print the case number in a line first. Then for each query rectangle, you have to answer the number of points that lie inside that rectangle. Print each of the results in separate lines.

1

5 6

0 0

5 9

2 3

4 6

7 7

0 0 5 9

2 2 10 11

4 6 7 9

3 3 4 5

4 6 5 7

5 7 7 9

Case 1:

4

4

3

0

1

2

# Note

Dataset is huge, use faster I/O methods.

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan