Range Sum Query on an Array

You are given an array (B) of size (M) and (T) queries. Each query contains two integers (L) and (R) (1-indexed). Your task is to compute the sum of the subarray from index (L) to (R) for each query. In mathematical notation, for a query ((L,R)), you need to calculate [ S(L,R)= \sum_{i=L}^{R} B_i = prefix[R]-prefix[L-1] ] where (prefix[i]) denotes the prefix sum of array (B) up to index (i).

Input is taken from standard input and output should be written to standard output.

inputFormat

The first line contains two integers (M) and (T), representing the size of the array and the number of queries, respectively. The second line contains (M) space-separated integers representing the array (B). This is followed by (T) lines, each containing two integers (L) and (R), representing the bounds of a query (1-indexed).

outputFormat

For each query, output the sum of the subarray from index (L) to (R) on a separate line.## sample

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

6
9
15