보물 찾기

시간 제한5초메모리 제한512 MB

요약

n개의 보물 좌표와 m개의 축에 나란한 직사각형이 주어질 때, 각 직사각형 안에 들어가는 보물의 개수를 센다.

난이도: 보통10점 중 6점
유형: 정렬, 이분 탐색, 누적 합, 기하
정답자: 아직 제출이 없습니다

문제

타로는 어떤 광장에 보물을 찾으러 왔다. 이 광장에는 보물이 많이 묻혀 있는데, 타로는 최신 기계를 가지고 있어서 어디에 보물이 묻혀 있는지 모두 알고 있다. 광장이 매우 넓어서 타로는 영역을 정해 보물을 찾기로 했지만, 보물이 많아 어떤 보물이 그 영역 안에 있는지 바로 알 수 없다. 그래서 타로는 그 영역 안에 있는 보물의 수를 세기로 했다.

입력

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

n은 광장에 묻혀 있는 보물의 수를 나타낸다.
m은 조사할 영역의 수를 나타낸다.
2번째 줄부터 n+1번째 줄은 각 보물이 묻혀 있는 좌표를 나타낸다.
n+2번째 줄부터 n+m+1번째 줄은 각각 조사할 영역을 나타낸다.
x축의 양의 방향이 동쪽, y축의 양의 방향이 북쪽을 나타낸다.
각 영역은 직사각형이며, xi1과 yi1은 직사각형의 남서쪽 꼭짓점 좌표, xi2와 yi2는 직사각형의 북동쪽 꼭짓점 좌표를 나타낸다.

출력

C1
C2
...
Cm

각 영역에 포함되는 보물의 수를 각 줄에 출력한다.

제한

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)
모든 입력은 정수로 주어진다.

예제4

예제 1
입력
```
3 1
1 1
2 4
5 3
0 0 5 5
```
예상 출력
```
3
```

예제 2

입력

예상 출력

2
1

예제 3

입력

예상 출력

2
2
0

예제 4

입력

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

예상 출력