Taco Word Count

In this problem, you are given the number of words written on each day over a period of (n) days and (q) queries. Each query consists of two integers (l) and (r) representing the starting and ending days respectively. Your task is to compute the sum of words written from day (l) to day (r) (both inclusive).

You can use the prefix sum technique to solve this efficiently. Define the prefix sum array (P) such that (P[i] = \sum_{j=1}^{i} a_j), where (a_j) is the number of words on day (j). Then the answer for a query ((l, r)) is given by (P[r] - P[l-1]) (with the convention that (P[0]=0)).

inputFormat

The first line contains two space-separated integers (n) and (q), where (n) is the number of days and (q) is the number of queries. The second line contains (n) space-separated integers, where each integer represents the number of words written on that day. The following (q) lines each contain two integers (l) and (r) representing a query.

outputFormat

For each query, output a single integer representing the sum of words written from day (l) to day (r). Each answer should be printed on a new line.## sample

5 3
5 10 15 20 25
1 3
2 4
1 5

30
45
75