// problem #35

구간 합 구하기

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지의 합을 구하는 프로그램을 작성하시오. 쿼리가 M개 주어진다.

입력

첫 줄에 N, M. 둘째 줄에 N개의 수. 이후 M개 줄에 각각 i, j.

출력

각 쿼리의 구간 합을 한 줄씩 출력한다.

제한

• 1 ≤ N, M ≤ 100,000
• 1 ≤ i ≤ j ≤ N
• 각 수는 1,000 이하의 자연수

예제

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

12
9
1