Taco: Subarray Sum Problem

Given an array of n integers and q queries, each query asks for the sum of elements in a subarray defined by its starting and ending indices. The indices are 1-indexed. To solve the problem efficiently, you may use the concept of prefix sums. For any query with indices \(l\) and \(r\), the answer can be computed as:

\[ S = \text{prefix}[r] - \text{prefix}[l-1] \]

Your task is to compute and output the sum for each query.

inputFormat

The first line contains two 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 (1-indexed) representing the starting and ending indices of the subarray.

outputFormat

For each query, output a single line containing an integer which is the sum of the subarray from index l to r.

## sample

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

6
9
15

</p>