세탁소의 첫 세탁 장부

문제

한 세탁소는 운영 기간 동안 매일 처리한 옷의 장수를 장부에 기록한다. 세탁소의 업무 보고서에는 처음 세탁한 옷과 다시 세탁한 옷을 구분해야 하지만, 오래된 장부에는 두 종류를 합친 처리 장수와 그중 재세탁한 장수만 남아 있다. 담당자는 이 장부를 이용하여 여러 기간의 첫 세탁 실적을 확인하려 한다. 운영일에는 1부터 N까지 차례대로 번호가 붙어 있다. i일의 기록은 전체 처리 장수 A_i와 재세탁 장수 B_i로 이루어진다. 이 날의 첫 세탁 장수는 A_i에서 B_i를 뺀 값이다. 재세탁 장수는 전체 처리 장수에 이미 포함되어 있으므로 두 값을 더해서는 안 된다. 각 날짜에는 같은 옷을 여러 번 처리하지 않으며, 서로 다른 날짜에 같은 옷이 등장하더라도 그 날짜에 기록된 구분을 그대로 따른다. 다른 날짜의 기록을 이용하여 옷의 이력을 추적할 필요는 없다. 담당자가 요청하는 조회는 시작일 L과 종료일 R로 주어진다. 조회 결과는 L일부터 R일까지 양 끝 날짜를 모두 포함하여 첫 세탁 장수를 더한 값이다. 예를 들어 첫 세탁 장수가 0인 날이 기간에 포함되더라도 그 날을 제외하고 날짜 번호를 다시 매기지 않는다. 시작일과 종료일이 같으면 해당 하루의 첫 세탁 장수만 구한다. 첫 세탁한 옷이 없는 기간의 결과는 0이다. 장부는 모든 조회에 걸쳐 동일하게 유지된다. 조회를 수행한다고 처리 장수가 줄어들지 않으며, 서로 겹치는 기간을 여러 번 물어볼 수도 있다. 또한 요청은 날짜순으로 주어진다는 보장이 없다. 프로그램은 모든 조회에 대해 입력된 순서대로 정확한 합계를 출력해야 한다. 날짜별 장부와 조회 목록이 주어졌을 때, 각 기간의 첫 세탁 실적을 계산하는 프로그램을 작성한다.

입력

첫째 줄에 운영일 수 N과 조회 수 Q가 공백으로 구분되어 주어진다. N과 Q는 정수이며, 1 ≤ N ≤ 30,000, 1 ≤ Q ≤ 15,000이다.
다음 N개의 줄 중 i번째 줄에는 정수 A_i와 B_i가 주어진다. 0 ≤ B_i ≤ A_i ≤ 9이다.
다음 Q개의 줄에는 정수 L과 R이 주어진다. 1 ≤ L ≤ R ≤ N이다. 같은 조회가 반복될 수 있다.

출력

각 조회마다 L일부터 R일까지의 첫 세탁 장수의 합을 한 줄에 하나씩 출력한다. 조회가 입력된 순서를 지키며, 합계가 0이면 0을 출력한다.

5 3
5 1
3 3
8 2
0 0
9 4
1 5
2 4
4 4

15
6
0

1 2
0 0
1 1
1 1

0
0

출처: Devin.KR 자체 제작