Range Sum Queries with Prefix Sum

You are given an array of integers and a set of queries. For each query, you need to compute the sum of the elements in the array between two given indices (inclusive). The indices are 1-indexed. This problem can be solved efficiently using the prefix sum technique.

Given an array (A) of length (n) and (q) queries, each query is defined by two integers (l_i) and (r_i) where (1 \leq l_i \leq r_i \leq n). For each query, calculate the sum: [ S = \sum_{i=l_i}^{r_i} A_i ]

Print the result for each query on a new line.

inputFormat

The first line contains two integers (n) and (q), where (n) is the length of the array and (q) is the number of queries. The second line contains (n) space-separated integers representing the array. The following (q) lines each contain two integers (l_i) and (r_i) representing a query.

outputFormat

For each query, output the computed sum of the elements from index (l_i) to (r_i) (inclusive) on a new line.## sample

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

6
9
15