천문대 관측 기록 포함 세기

문제

한 천문대는 망원경으로 별을 관측한 기록을 N개 보관하고 있다. i번째 기록은 관측을 시작한 시각 s_i와 끝낸 시각 e_i로 이루어지며, s_i ≤ e_i인 정수이다. 서로 다른 기록의 시작이나 끝 시각이 같을 수도 있고, 완전히 똑같은 기록이 여러 번 있을 수도 있다. 연구원들은 Q개의 점검 구간을 차례로 확인하려 한다. j번째 점검 구간은 두 정수 L_j, R_j로 주어지며, 어떤 기록이 이 점검 구간에 포함된다는 것은 L_j ≤ s_i 이고 e_i ≤ R_j 인 경우를 말한다. 경계가 같아도 포함된 것으로 센다. 각 점검 구간마다 그 구간에 포함되는 기록이 몇 개인지 구하라. 점검 구간끼리는 서로 영향을 주지 않으며, 기록은 질의 때문에 바뀌지 않는다. 포함되는 기록이 하나도 없으면 0을 출력한다. 모든 점검 구간의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력하라.

입력

첫 줄에 두 정수 N, Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200000, 1 ≤ Q ≤ 200000)
다음 N개의 줄에 각각 두 정수 s_i, e_i가 주어진다. (1 ≤ s_i ≤ e_i ≤ 10^9)
다음 Q개의 줄에 각각 두 정수 L_j, R_j가 주어진다. (1 ≤ L_j ≤ R_j ≤ 10^9)

출력

Q개의 줄에 걸쳐, j번째 줄에 j번째 점검 구간에 포함되는 기록의 수를 출력한다.

5 3
1 4
2 3
3 9
5 6
5 5
1 6
2 5
6 10

4
2
0

2 2
7 7
7 7
7 7
1 6

2
0

출처: Devin.KR 자체 제작