Range Sum Queries

Statement

You are given an array of n integers and q queries. Each query gives two indices l and r. For each query, print the sum of the elements from position l to position r, inclusive.

Input

The first line has n and q. The second line has n integers. Each of the next q lines has l and r (1-indexed).

Output

For each query, print one line with the sum.

Constraints

1 <= n, q <= 200000
1 <= l <= r <= n
|a_i| <= 10^9

Example 1

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

7
13
5

2+4+1 = 7, 4+1+5+3 = 13, and the last query is the single element 5.