카페 적립금 장부

문제

작은 카페는 영업이 끝날 때마다 그날의 적립금 변동량을 장부에 기록한다. 손님에게 새로 지급한 적립금은 양수로, 손님이 사용하여 차감한 적립금은 음수로 기록한다. 지급한 금액과 사용한 금액이 같으면 그날의 기록은 0이다. 장부에는 첫째 날부터 N번째 날까지 하루에 하나씩, 모두 N개의 정수가 순서대로 적혀 있다. 카페 관리자는 여러 정산 기간을 확인하려 한다. 하나의 정산 기간은 시작일 L과 종료일 R로 정해지며, L번째 날과 R번째 날을 모두 포함한다. 해당 기간의 순변동량은 이 기간에 기록된 모든 정수를 더한 값이다. 순변동량이 양수이면 그만큼 적립금이 늘어났고, 음수이면 그 절댓값만큼 줄어든 것이다. 기간 중간에 합계가 음수가 되어도 계산을 멈추거나 합계를 0으로 바꾸지 않는다. 각 정산 요청은 다른 요청과 독립적이다. 어떤 요청을 처리하더라도 장부의 기록은 바뀌지 않으며, 이전 요청에서 계산한 결과를 다음 요청의 시작 금액으로 사용하지 않는다. 서로 겹치는 기간이나 완전히 같은 기간이 여러 번 주어질 수도 있다. 시작일과 종료일이 같다면 그날의 기록 하나만 계산에 포함한다. 관리자는 요청한 기간의 길이나 날짜별 내역 대신 순변동량 하나만 확인하면 된다. 따라서 결과를 양수 부분과 음수 부분으로 나누거나, 결과의 절댓값을 출력해서는 안 된다. 합계가 정확히 0이면 0을 출력한다. 장부와 Q개의 정산 요청이 주어질 때, 각 요청에 대한 순변동량을 입력된 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 50,000이며 1 ≤ Q ≤ 10,000이다.
둘째 줄에 각 날짜의 적립금 변동량을 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 -99 ≤ A_i ≤ 99이다.
다음 Q개의 줄에는 정수 L과 R이 공백으로 구분되어 주어진다. 각 요청은 1 ≤ L ≤ R ≤ N을 만족한다.

출력

각 요청에 대해 L번째 날부터 R번째 날까지의 적립금 변동량 합을 한 줄에 하나씩 출력한다. 음수인 결과에는 음수 부호를 붙이며, 양수인 결과에는 별도의 부호를 붙이지 않는다.

6 4
12 -5 0 8 -20 7
1 3
2 5
4 4
1 6

7
-17
8
2

3 3
-9 0 9
1 3
1 1
2 2

0
-9
0

출처: Devin.KR 자체 제작