구간 합 구하기

첫 줄에 수의 개수 n (1 이상 100000 이하) 과 질의의 개수 q (1 이상 100000 이하) 가 주어집니다. 둘째 줄에 n개의 수가 주어집니다. 각 수는 1 이상 1000 이하입니다. 이어서 q개의 줄에 각각 두 정수 l 과 r (1 이상 n 이하, l ≤ r) 이 주어집니다.

각 질의마다 l번째부터 r번째까지의 수의 합을 한 줄에 하나씩 출력하세요. (1번부터 셉니다.)

예시

입력

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

출력

6
9
15