누적 합 구간 쿼리

N개의 정수가 주어진다. Q개의 쿼리가 주어지며, 각 쿼리는 구간 [L, R]의 합을 묻는다. 누적 합(prefix sum)을 미리 계산하여 각 쿼리에 O(1)로 답하라.

인덱스는 1-based이다.

입력

첫째 줄에 N과 Q가 공백으로 구분되어 주어진다.
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다.
이후 Q개의 줄에 각각 L과 R이 공백으로 구분되어 주어진다.

• 1 ≤ N, Q ≤ 100,000
• -10,000 ≤ 각 정수 ≤ 10,000
• 1 ≤ L ≤ R ≤ N

출력

각 쿼리마다 A[L] + A[L+1] + ... + A[R]을 한 줄에 출력한다.

예제 입력 1

10 3
3 1 4 1 5 9 2 6 5 3
1 5
3 8
1 10

예제 출력 1

14
27
39