순환 생산 라인의 검사 구간

문제

한 공장의 생산 라인은 원형으로 연결된 N개의 작업 칸으로 이루어져 있다. 작업 칸에는 진행 방향을 따라 1번부터 N번까지 번호가 붙어 있으며, N번 칸의 다음 칸은 1번 칸이다. 하루의 생산을 마친 뒤 각 칸에는 그 칸에서 완성한 제품이 놓여 있다. i번 칸의 제품 수를 A_i라고 하며, 제품이 하나도 없는 칸도 있을 수 있다. 검사하는 동안 제품이 이동하거나 제품 수가 바뀌는 일은 없다. 품질 담당자는 여러 검사 구간에 대해 확인해야 할 제품 수를 계산하려 한다. 검사 구간 하나는 시작 칸 L과 마지막 칸 R로 지정한다. 검사자는 L번 칸의 제품을 확인한 뒤 번호가 증가하는 방향으로 이동하고, R번 칸의 제품까지 확인하면 즉시 검사를 끝낸다. 검사 구간에는 시작 칸과 마지막 칸이 모두 포함된다. 이동 중 N번 칸 다음으로 가야 한다면 1번 칸으로 이어서 이동한다. L이 R보다 작으면 L번부터 R번까지의 칸을 확인한다. L이 R보다 크면 L번부터 N번까지 확인한 뒤 1번부터 R번까지 확인한다. L과 R이 같을 때는 그 칸 하나만 확인한다. 이 경우 생산 라인을 한 바퀴 도는 것으로 해석하지 않는다. 따라서 하나의 검사 구간에서 같은 칸을 두 번 확인하는 일은 없다. 검사 요청은 서로 독립적이다. 앞선 요청에서 확인한 제품도 다른 요청의 검사 구간에 포함되면 다시 계산에 넣는다. 실제로 제품을 꺼내거나 제거하는 작업은 하지 않는다. 같은 시작 칸과 마지막 칸을 가진 요청이 여러 번 나타날 수도 있으며, 각 요청에 대한 결과를 입력 순서대로 모두 출력해야 한다. 각 칸의 제품 수와 Q개의 검사 요청이 주어진다. 담당자가 모든 구간을 매번 따라가며 세지 않아도 되도록, 각 요청에서 확인하는 제품 수의 합을 구한다. 모든 칸의 제품 수가 0일 수도 있으며, 이 경우에도 요청마다 합계 0을 출력한다.

입력

첫째 줄에 작업 칸의 수 N과 검사 요청의 수 Q가 공백으로 구분되어 주어진다. N은 1 이상 40,000 이하, Q는 1 이상 15,000 이하의 정수다.
둘째 줄에 각 칸의 제품 수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 0 이상 999 이하의 정수다.
다음 Q개의 줄에 검사 요청의 시작 칸 L과 마지막 칸 R이 공백으로 구분되어 주어진다. L과 R은 각각 1 이상 N 이하의 정수다.

출력

각 검사 요청에서 확인하는 제품 수의 합을 입력 순서대로 한 줄에 하나씩 출력한다. L=R인 요청에서는 A_L을 출력한다.

5 4
3 0 7 2 4
2 4
4 2
3 3
1 5

9
9
7
16

1 3
0
1 1
1 1
1 1

0
0
0

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

13
14
14

출처: Devin.KR 자체 제작