Range Sum Query Using Prefix Sum

You are given an array of n integers and m queries. For each query, you need to compute the sum of the elements of the array in the range [l, r].

To achieve an efficient solution, use a prefix sum array. The prefix sum array P is defined as:

$$ P[i] = P[i-1] + \text{array}[i-1] \quad \text{for} \quad 1 \le i \le n, \quad \text{with} \quad P[0]=0. $$

Then, the sum of a subarray from index l to r (1-indexed) can be computed in O(1) time using the formula:

$$ \text{sum}(l, r) = P[r] - P[l-1]. $$

Your task is to implement this using the given input and output format.

inputFormat

The input is given from standard input in the following format: The first line contains two integers n and m, where n is the number of elements in the array and m is the number of queries. The second line contains n integers separated by spaces, representing the array elements. The following m lines each contain two integers l and r, representing a query to compute the sum of elements from index l to r (1-indexed).

outputFormat

For each query, output the computed sum on a new line to standard output.## sample

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

6
14
15