Range Sum Queries

You are given an array of N integers and Q queries. For each query, you are given two integers L and R (1-indexed) representing the starting and ending positions of a subarray. Your task is to compute the sum of the subarray from index L to R.

To solve this problem efficiently, precompute the prefix sums of the array. The prefix sum array P is defined as:

\(P[0] = 0, \quad P[i] = \sum_{j=1}^{i} a_j \quad (1 \leq i \leq N)\)

Then the sum for any query [L, R] can be computed as:

\(\text{Sum} = P[R] - P[L-1]\)

Input: The input consists of multiple lines. The first line contains two integers N and Q. The second line contains N space-separated integers representing the array elements. Each of the next Q lines contains two integers L and R.

Output: For each query, output a single integer on a new line representing the sum of the subarray from index L to R.

inputFormat

The first line contains two integers N (the number of elements in the array) and Q (the number of queries). The second line contains N space-separated integers. Each of the following Q lines contains two integers L and R (1-indexed) representing the query range.

outputFormat

For each query, output a single integer on a new line, which is the sum of the elements in the subarray from index L to R.## sample

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

6
9
15