이름표

일자로 길게 늘어진 하나의 선이 있다. 이 선 위에는 1부터 300,000까지의 각 수가 왼쪽부터 오른쪽까지 차례대로 적혀있다. 각 수의 아래에는 학생들이 이름표를 붙일 수 있는 공간이 존재한다.

총 N명의 학생은 각자 원하는 시작 지점(수)부터 시작하여 원하는 끝 지점(수)까지의 모든 연속된 수 아래에 자신의 이름표를 붙인다. 이때 학생의 수 N은 1 이상 300,000 이하의 값을 가지며, 각 학생에 대하여 구간의 길이는 최대 300,000의 값을 가질 수 있다. 이때, 구간의 길이란 해당 학생이 붙이게 되는 이름표의 개수를 의미한다.

이때, 각 학생에 대하여 [시작 지점 t, 구간의 길이 k] 정보가 주어진다고 해보자. 한 학생의 시작 지점이 500이고, 구간의 길이가 10이라면 500이상 509 이하의 모든 수의 위치에 대하여 자신의 이름표를 붙이는 것이다.

단, 구간을 설정함으로써 범위를 벗어나는 지점에는 이름을 붙이지 않는다. 예를 들어 특정한 학생이 시작 지점을 299,995로 설정하고, 구간의 길이를 100으로 설정한 경우를 생각하자. 이 경우 100개의 위치가 아니라 299,995, 299,996, 299,997, 299,998, 299,999, 300,000까지 총 6개 지점의 위치에 대해서만 이름표를 붙이게 된다.

N명의 학생이 이름표를 모두 붙이고 나면, 이후에 M개의 질의(query)가 수행된다. 질의의 수 M은 최대 100,000이다. 각 질의는 [start, end] 형태로 구성되는데, 구체적으로 start 이상 end 이하의 모든 수에 대하여 그 수의 아래에 존재하는 이름표 개수의 합을 구하는 것을 의미한다. 단, start는 1 이상 300,000 이하의 자연수다. 또한 end는 start 이상 300,000 이하의 자연수다. M개의 질의(query)에 대하여 각각 구간에 속한 이름표의 개수의 총 합을 계산하고, 그 결과를 크기가 M인 1차원 배열로 반환하는 프로그램을 작성하여라.

예를 들어 N=5, M=3이고, 각 학생이 선에 이름표를 거는 작업에 대한 정보가 다음의 표와 같다고 해보자.

위 예시와 같이 1번부터 5번 학생까지 차례대로 이름표를 걸었다고 해보자. 그러면 선 위의 각 수(위치)에 대하여 다음과 같이 이름표들이 걸리게 될 것이다.

이후에 각 3개의 쿼리에 대한 정보가 차례대로 [3, 7], [7, 9], [2, 5]라고 가정하자. 이때 각 쿼리에 대한 정답을 포함해 표 형태로 정리하여 나타내면 다음과 같다.

따라서, 현재 예시에서는 [16, 5, 13]이 정답이다.

입출력 예시

예시 1

입력

5, 3, [[3, 2], [6, 3], [2, 8], [1, 5], [3, 4]], [[3, 7], [7, 9], [2, 5]]

출력

[16, 5, 13]

원본에서 모의고사 8회 2번입니다.