수족관의 원형 먹이 통로

문제

수족관의 먹이 운반 통로는 여러 수조를 따라 원형으로 이어져 있다. 통로를 따라 시계 방향으로 수조에 1부터 N까지 번호를 붙였다. i번 수조 바로 다음에는 i+1번 수조가 있으며, N번 수조 바로 다음에는 1번 수조가 있다. 각 수조에는 오늘 공급해야 하는 먹이의 양이 정수로 기록되어 있다. 관리자는 운반 카트가 이동할 구간에 필요한 먹이의 총량을 미리 확인하려 한다. 하나의 조회는 시작 수조 s와 마지막 수조 t로 주어진다. 카트는 s번 수조에서 출발하여 시계 방향으로 이동하고, t번 수조를 처음 방문하면 그곳에서 이동을 끝낸다. 출발 수조와 마지막 수조에 필요한 먹이를 모두 합산한다. s와 t가 같으면 해당 수조 하나만 방문한다. 예를 들어 수조가 여섯 개일 때 시작 수조가 5이고 마지막 수조가 2이면 5번, 6번, 1번, 2번 수조를 차례로 방문한다. 마지막 수조에 도착한 뒤 추가로 한 바퀴를 돌지는 않는다. 따라서 어떤 조회에서도 같은 수조의 먹이를 두 번 합산하지 않는다. 시작 수조가 1이고 마지막 수조가 N이면 모든 수조를 정확히 한 번 방문한다. 조회는 실제 먹이 공급이 아니라 운반 계획을 위한 계산이다. 앞선 조회에서 어떤 수조를 방문했더라도 그 수조의 먹이 양은 줄어들지 않는다. 모든 조회는 처음 입력된 동일한 먹이 목록을 기준으로 서로 독립적으로 처리한다. 먹이가 필요하지 않은 수조의 양은 0이며, 구간에 포함된 모든 수조의 양이 0이면 총량도 0이다. 각 조회에 대하여 카트가 방문하는 수조들에 필요한 먹이의 총량을 구하는 프로그램을 작성한다. 조회 결과는 입력된 순서대로 출력해야 한다. 서로 다른 조회의 총량이 같아도 각각 출력하며, 결과가 크더라도 나머지를 구하거나 반올림하지 않고 정확한 정수를 출력한다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1≤N≤15,000, 1≤Q≤15,000이다.
둘째 줄에 각 수조의 먹이 양을 나타내는 정수 A1, A2, …, AN이 주어진다. 0≤Ai≤1,000,000이다.
다음 Q개 줄에는 조회의 시작 수조와 마지막 수조를 나타내는 정수 s, t가 주어진다. 1≤s,t≤N이다.

출력

각 조회에 대한 먹이 총량을 입력 순서대로 한 줄에 하나씩 출력한다.

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

9
10
7
17

1 2
0
1 1
1 1

0
0

출처: Devin.KR 자체 제작