Server Time: Thu Aug 6, 2020 10:43 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 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).


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.

Sample Input

Output for Sample Input


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:








Dataset is huge, use faster I/O methods.

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