편의점 정산 구간 조회

문제

여러 편의점의 정산 자료를 관리하는 데이터 담당자가 하나로 합쳐진 거래 파일을 받았다. 파일에는 거래가 수집된 순서대로 행이 들어 있으며, 각 행에는 점포 번호와 정산 금액이 기록되어 있다. 판매로 정산 금액이 늘어나는 경우에는 양수가, 환불이나 정정으로 줄어드는 경우에는 음수가 기록된다. 금액이 0인 행도 유효한 거래 행이다. 같은 점포의 거래가 연속해서 나타난다는 보장은 없다. 담당자는 원본 파일을 수정하지 않고 여러 구간의 정산 금액을 확인해야 한다. 각 조회는 점포 번호와 시작 행 번호, 끝 행 번호로 이루어진다. 해당 행 번호 구간에 포함되면서 점포 번호까지 일치하는 거래의 금액만 모두 더한 값이 조회 결과이다. 시작 행과 끝 행도 합산 대상에 포함한다. 다른 점포의 거래는 구간 안에 있더라도 합산하지 않는다. 행 번호는 모든 점포의 거래를 합친 원본 거래 영역을 기준으로 위에서부터 1번부터 매긴다. 특정 점포의 거래만 추려 낸 뒤 새롭게 번호를 붙이는 것이 아니다. 입력의 첫째 줄이나 조회 영역의 줄에는 거래 행 번호를 부여하지 않는다. 같은 점포와 같은 금액을 가진 행이 여러 개 있더라도 서로 다른 행이므로 각각 합산한다. 조회 구간에 해당 점포의 거래가 없다면 결과는 0이다. 거래 영역과 조회 영역은 쉼표로 열을 구분한 표 형식이다. 이 문제에서는 모든 셀이 정수이고 따옴표, 빈 셀, 셀 내부의 쉼표는 없다. 첫째 줄의 개수 정보를 이용하면 두 영역을 구분할 수 있다. 모든 조회는 같은 원본 거래 자료를 대상으로 하며, 조회를 수행해도 거래가 삭제되거나 금액이 바뀌지 않는다. 담당자가 각 조회 결과를 입력된 순서대로 얻을 수 있도록 프로그램을 작성해야 한다.

입력

첫째 줄에 거래 수 N과 조회 수 Q가 공백으로 구분되어 주어진다. N과 Q는 정수이며 1 ≤ N ≤ 50,000, 1 ≤ Q ≤ 5,000이다.
다음 N개 줄은 점포번호,금액 형식이다. 점포 번호는 0 이상 9 이하인 정수이고, 금액은 -1,000,000,000 이상 1,000,000,000 이하인 정수이다.
다음 Q개 줄은 점포번호,L,R 형식이다. 각 값은 정수이며 점포 번호는 0 이상 9 이하이고 1 ≤ L ≤ R ≤ N이다.
CSV 영역에는 공백과 머리글이 없다. 정수는 불필요한 앞자리 0이나 더하기 기호 없이 표기하며 음수에만 빼기 기호를 붙인다. 0은 0으로 표기한다.

출력

각 조회의 합계를 입력된 순서대로 한 줄에 하나씩 정수로 출력한다. 조건에 맞는 거래가 없다면 0을 출력한다.

6 4
2,80
1,30
2,-15
2,0
1,-10
2,25
2,2,6
1,1,4
3,1,6
2,1,1

10
30
0
80

3 3
0,-7
0,-7
9,4
0,1,2
9,1,2
9,3,3

-14
0
4

출처: Devin.KR 자체 제작