한 바퀴 안의 재생 시간

문제

음악 스트리밍 서비스에서 사용자가 만든 재생 목록에는 N개의 곡이 들어 있다. 곡에는 목록에 놓인 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 곡의 재생 시간은 초 단위의 양의 정수다. 제목이나 재생 시간이 같은 곡이 여러 번 들어 있어도 목록의 서로 다른 위치에 있는 곡으로 취급한다. 이 재생 목록은 반복 재생하도록 설정되어 있다. 1번 곡부터 번호가 커지는 방향으로 재생하며, N번 곡이 끝나면 다시 1번 곡을 재생한다. 곡 사이에 쉬는 시간은 없고, 곡을 겹쳐 재생하거나 일부를 건너뛰는 기능도 사용하지 않는다. 각 곡은 입력으로 주어진 재생 시간만큼 처음부터 끝까지 재생한다. 사용자는 특정 구간을 듣는 데 걸리는 시간을 여러 번 확인하려 한다. 질문 하나에는 시작 곡 번호 L과 마지막 곡 번호 R이 주어진다. 이 질문의 구간은 L번 곡의 시작에서 출발하여 목록의 재생 방향으로 진행한 뒤, R번 곡을 처음으로 끝까지 재생한 순간에 종료한다. 시작 곡과 마지막 곡의 재생 시간을 모두 포함한다. L이 R보다 작거나 같으면 L번부터 R번까지의 곡을 차례로 듣는다. L이 R보다 크면 L번부터 N번까지 들은 다음 1번으로 돌아가 R번까지 듣는다. 특히 L과 R이 같으면 그 곡 하나만 듣는 구간이다. 같은 번호로 돌아올 때까지 목록 전체를 듣는다는 뜻이 아니다. 질문들은 서로 독립적이다. 앞선 질문에서 재생이 끝난 위치는 다음 질문에 영향을 주지 않으며, 질문을 처리하는 동안 목록의 순서나 곡의 재생 시간이 바뀌지 않는다. 각 질문에 대해 해당 구간의 전체 재생 시간을 초 단위로 계산하는 프로그램을 작성한다.

입력

첫째 줄에 곡 수 N과 질문 수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 20,000)
둘째 줄에 각 곡의 재생 시간 D_1, D_2, …, D_N이 주어진다. 각 D_i는 1 이상 600 이하의 정수다.
다음 Q개 줄에 질문의 시작 곡 번호 L과 마지막 곡 번호 R이 주어진다. L과 R은 각각 1 이상 N 이하의 정수다.

출력

각 질문의 전체 재생 시간을 초 단위의 정수로 한 줄에 하나씩, 질문이 주어진 순서대로 출력한다.

5 3
120 75 210 90 150
2 4
4 2
3 3

375
435
210

1 2
600
1 1
1 1

600
600

4 3
10 10 10 10
1 4
4 1
2 1

40
20
40

출처: Devin.KR 자체 제작