N개의 정수로 이루어진 수열 Ai가 주어진다. 이때, 수열의 특정 구간 [i, j]가 주어졌을 때 해당 구간에 속하는 수들의 합을 구하는 프로그램을 작성하시오. 수열의 인덱스는 1부터 시작한다.

입력

첫째 줄에 수열의 크기 N과 합을 구해야 하는 횟수 Q가 공백을 사이에 두고 주어진다.

둘째 줄에는 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.

셋째 줄부터 Q개의 줄에 걸쳐 합을 구해야 하는 구간을 의미하는 두 정수 i, j가 주어진다.

출력

Q개의 줄에 걸쳐, 각 줄마다 입력으로 주어진 i번째 수부터 j번째 수까지의 합을 출력한다.

제약 조건

1 ≤ N ≤ 100000

1 ≤ Q ≤ 100000

-1000 ≤ Ai ≤ 1000

1 ≤ i ≤ j ≤ N

예제 입력 1

6 3
5 4 3 2 -1 8 
1 6
5 5
2 5

예제 출력 1

21
-1
8