시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 98 35 25 50.000%

문제

승관이와 영우는 앞으로 Q일 동안 점심을 같이 먹기로 했다. 

승관이는 [u, v] 구간의 매운맛을 좋아하고 영우는 [x, y] 구간의 단맛을 좋아한다. (u, v, x, y는 매일 매일 기분 따라 바뀐다) 

N가지 점심 메뉴의 매운맛 수치 a와, 단맛 수치 b가 주어지고, 앞으로 Q 일간의 u, v, x, y가 주어진다. 

승관이와 영우의 점심 메뉴 선택을 돕기 위해, 날마다 승관이와 영우가 둘 다 좋아하는 메뉴의 수를 알려주는 프로그램을 만들어주자.

입력

입력의 첫 줄에 점심 메뉴의 수 N(1 ≤ N ≤ 10만)과, 점심을 같이 먹는 기간 Q(1 ≤ Q ≤ 5000)가 주어진다. 

둘째 줄부터 N개의 줄에 각 메뉴의 매운맛, 단맛 수치인 a, b가 주어진다. (1≤ a, b ≤ 10억) 

a, b값은 유니크하다. 즉 같은 a 값을 가지는 서로 다른 두 메뉴는 없고, 같은 b 값을 가지는 서로 다른 두 메뉴도 없다. 

그 다음 줄부터 Q개의 줄에 각 날의 u, v, x, y가 주어진다. (1 ≤ u ≤ v ≤ 10억, v ≤ u + 10000, 1 ≤ x ≤ y ≤ 10억, y ≤ x + 10000) 

출력

Q개의 줄에 줄마다 각 날의 영우와 승관이가 둘 다 좋아하는 메뉴의 수, 즉 u ≤ a ≤ v 이고, x ≤ b ≤ y 인 메뉴의 수를 출력한다 

예제 입력 1

6 4
10 50
30 30
20 70
60 20
70 40
100 10
1 1000 10 70
10 30 50 70
10 100 20 20
30 99 1 39

예제 출력 1

6
2
1
2

힌트

출처