Subarray Sum Queries

This problem requires you to efficiently compute the sum of a subarray for a given query range. You are given an array A of N integers in 1-indexed format, and Q queries. Each query provides two integers, L and R, and you must compute the sum of the subarray from index L to R inclusive.

You can use the prefix sum technique where the prefix sum P is defined as:

$P[i] = \sum_{j=1}^{i} A[j]$

Then the sum of the subarray for indices L and R can be computed as:

$\text{sum} = P[R] - P[L-1]$

Input is read from standard input and output should be written to standard output, with each result printed on a separate line.

inputFormat

The first line contains two integers N and Q separated by a space, where N is the number of elements in the array and Q is the number of queries.

The second line contains N integers separated by spaces, representing the array A.

The next Q lines each contain two integers L and R, representing a query to compute 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

4 1
10 20 30 40
2 4

90

</p>