10118 구간 합 구하기 4 Silver III

문제

N개의 수와 M개의 구간 합 쿼리가 주어진다.

입력

첫째 줄에 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에 N개의 수가 주어진다. 다음 M줄에 i, j가 주어진다.

출력

각 쿼리마다 i번째 수부터 j번째 수까지의 합을 출력한다.

5 3
10 20 30 40 50
1 3
2 4
1 5

60
90
150