길이가 N 인 수열 A_1, A_2, ..., A_N 이 주어질 때, 수열의 L 번째 원소부터 R 번째 원소까지의 합을 구해보자.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 10 000) 이 주어진다.

둘째 줄에 정수 A_1, A_2, ..., A_N (-100 ≤ A_i ≤ 100) 이 주어진다.

셋째 줄부터 M 개의 줄에 L, R (1 ≤ L ≤ R ≤ N) 이 주어진다.

출력

M개의 줄에 수열의 L 번째 원소부터 R 번째 원소까지의 합을 출력한다.

예제 입력

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

예제 출력

1
3
6
10
2
5
9
3
7
4

추가 설명

입력의 범위가 작기 때문에 누적 합 자료 구조를 사용하지 않아도 해결할 수 있다.