Treasure Hunt

Time limit5sMemory limit512 MB

Summary

Given n treasure points and m axis-aligned rectangles, count how many points fall inside each rectangle (boundaries included).

Level: Medium6 of 10
Topics: Sorting, Binary search, Prefix sum, Geometry
Solved: No attempts yet

Problem

Taro has come to a plaza to look for treasure. Many treasures are buried in this plaza, and since Taro has a state-of-the-art machine, he knows exactly where every treasure is buried. The plaza is very large, so Taro decided to pick a region and search for treasure there, but there are so many treasures that he cannot immediately tell which ones lie inside that region. So Taro decided to count the number of treasures inside the region.

Input

n m
x1 y1
x2 y2
...
xn yn
x11 y11 x12 y12
x21 y21 x22 y22
...
xm1 ym1 xm2 ym2

n is the number of treasures buried in the plaza.
m is the number of regions to examine.
Lines 2 through n+1 give the coordinates where each treasure is buried.
Lines n+2 through n+m+1 give each region to examine.
The positive x direction is east, and the positive y direction is north.
Each region is a rectangle, where xi1 and yi1 are the coordinates of the southwest vertex, and xi2 and yi2 are the coordinates of the northeast vertex.

Output

C1
C2
...
Cm

Print the number of treasures contained in each region, one per line.

Constraints

1 ≤ n ≤ 5000
1 ≤ m ≤ 5×105
|xi|, |yi| ≤ 109 (1 ≤ i ≤ n)
|xi1|, |yi1|, |xi2|, |yi2| ≤ 109 (1 ≤ i ≤ m)
xi1 ≤ xi2, yi1 ≤ yi2 (1 ≤ i ≤ m)
All input is given as integers.

Examples4

Example 1
Input
```
3 1
1 1
2 4
5 3
0 0 5 5
```
Expected output
```
3
```

Example 2

Input

Expected output

2
1

Example 3

Input

Expected output

2
2
0

Example 4

Input

5 5
10 5
-3 -8
2 11
6 0
-1 3
-3 1 3 13
-1 -1 9 5
-3 -8 10 11
0 0 5 5
-10 -9 15 10

Expected output