Range Sum Queries

In this problem, you are given an integer array of size (n) and (q) queries. Each query consists of two integers (l) and (r) representing indices (1-indexed), and you are required to compute the sum of the array elements in the range ([l, r]).

The sum for a given query can be defined as:
[ S = \sum_{i=l}^{r} a_i ] where (a_i) is the (i)th element of the array.

This problem can be solved efficiently using prefix sums.

inputFormat

The first line contains two space-separated integers (n) and (q), where (n) is the number of elements in the array and (q) is the number of queries. The second line contains (n) space-separated integers representing the array elements. Each of the following (q) lines contains two space-separated integers (l) and (r), denoting the query range (1-indexed).

outputFormat

For each query, print the sum of the array elements from index (l) to (r) on a new line.## sample

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

60
90
150