Calculate Total Water

You are given N wells and Q queries. The i-th well contains a certain amount of water. Each query is represented by a pair of integers \(L\) and \(R\), and you need to compute the total amount of water in the wells from index \(L\) to \(R\) (inclusive). Indices are 0-indexed.

To facilitate efficient queries, you might consider using a prefix sum array such that the sum on the interval \([L, R]\) is computed using the formula:

[ prefix[R+1] - prefix[L] ]

Implement a solution that reads the input from standard input and prints the results to standard output.

inputFormat

The first line contains two space-separated integers \(N\) and \(Q\), where \(N\) is the number of wells and \(Q\) is the number of queries.

The second line contains \(N\) space-separated integers, representing the amount of water in each well.

The following \(Q\) lines each contain two space-separated integers \(L\) and \(R\) representing a query.

outputFormat

Output \(Q\) lines. The \(i\)-th line should contain a single integer, the total amount of water in the interval specified by the \(i\)-th query.

## sample

10 3
5 3 8 6 2 9 4 7 1 3
2 5
0 3
7 9

25
22
11

</p>