Subarray Sums

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

Mathematical Formulation:

Given an array A and a query (L, R), you need to compute:

\[ S = \sum_{i=L}^{R} A_i \]

Input Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ A[i] ≤ 10⁹
• 1 ≤ L ≤ R ≤ N

Example:

Input:
5 3
1 2 3 4 5
1 3
2 4
1 5
Output:
6
9
15

</p>

inputFormat

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

The second line contains N space-separated integers, representing the array A.

Each of the following Q lines contains two integers L and R, representing a query asking for the sum of the subarray from index L to R (inclusive, 1-indexed).

outputFormat

For each query, output a single line containing 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>