Subarray Sum Queries

You are given an array of n integers and q queries. For each query, you are given two indices l and r (1-indexed). Your task is to compute the sum of the elements in the subarray from index l to r inclusive.

A common approach is to use a prefix sum array. The prefix sum array P is defined as:

( P[i] = \sum_{j=1}^{i} a_j ) for ( i \geq 1 ) with ( P[0]=0 ).

The sum for a query from l to r can then be computed as:

( S = P[r] - P[l-1] ).

This problem is an easy one, and an efficient solution can be implemented in \( O(n + q) \) time.

inputFormat

The first line contains two integers n and q separated by a space, representing the number of elements in the array and the number of queries respectively.

The second line contains n integers separated by space, representing the array elements.

Each of the next q lines contains two integers l and r separated by space, representing a query for the sum of the subarray from index l to r (1-indexed).

outputFormat

For each query, output the sum of the subarray on a new line.

## sample

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

6
9
15

</p>