게임 서버의 틱 기록

문제

한 게임 서버는 실행 시간을 같은 길이의 작은 구간인 틱으로 나누어 관리한다. 운영 도구에는 연속한 N개 틱의 기록이 저장되어 있고, 오래된 틱부터 차례로 1번부터 N번까지 번호가 붙어 있다. 각 기록에는 해당 틱에서 처리가 완료된 보상 요청의 수가 적혀 있다. 한 틱에서 완료된 요청의 수는 0 이상 9 이하의 정수이다. 요청이 서버에 도착한 시점과 처리가 완료된 시점은 다를 수 있다. 이 도구에서는 오직 처리가 완료된 틱에만 그 요청을 한 번 센다. 따라서 각 틱의 기록에 적힌 수를 그대로 사용하면 되며, 요청의 도착 시점이나 이용자 정보는 따로 고려하지 않는다. 기록이 0인 틱도 정상적인 기록이며 번호에서 빠지지 않는다. 운영자는 특정 구간에 서버가 얼마나 많은 요청을 처리했는지 확인하려 한다. 확인 요청 하나에는 두 틱 번호 L과 R이 들어 있다. 그 요청의 답은 L번 틱부터 R번 틱까지 완료된 보상 요청의 총수이다. 양 끝에 있는 L번 틱과 R번 틱의 기록도 모두 포함한다. L과 R이 같다면 해당 틱 하나의 기록이 답이 된다. 운영 도구에는 이러한 확인 요청이 Q개 들어온다. 서로 다른 확인 요청의 구간은 겹칠 수 있고, 같은 구간이 여러 번 등장할 수도 있다. 확인 요청은 기록을 조회하기만 하므로 어떤 답을 구한 뒤에도 저장된 수는 바뀌지 않는다. 각 확인 요청은 다른 요청과 독립적으로 처리해야 한다. 틱별 기록과 모든 확인 요청이 주어질 때, 각 구간에서 완료된 보상 요청의 총수를 입력된 확인 요청의 순서대로 출력하는 프로그램을 작성하라. 모든 확인 요청에는 유효한 틱 번호가 주어지므로 답이 없는 경우는 없다. 구간에 있는 모든 기록이 0이라면 그 요청의 답은 0이다.

입력

첫째 줄에 정수 N과 Q가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20000, 1 ≤ Q ≤ 20000이다.
둘째 줄에 정수 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다. a_i는 i번 틱에서 완료된 요청의 수이며 0 ≤ a_i ≤ 9이다.
다음 Q개 줄에는 확인 요청을 나타내는 정수 L과 R이 공백으로 구분되어 주어진다. 각 요청은 1 ≤ L ≤ R ≤ N을 만족한다.

출력

각 확인 요청마다 L번 틱부터 R번 틱까지의 기록을 모두 더한 정수를 한 줄에 하나씩 출력한다. 확인 요청이 입력된 순서를 지켜야 한다.

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

5
8
1

4 3
0 0 0 0
1 4
2 2
1 4

0
0
0

1 2
9
1 1
1 1

9
9

출처: Devin.KR 자체 제작