Total Weight in Ranges

You are given n coins with weights w₁, w₂, …, w_n and q queries. Each query is represented by two integers l and r (1-indexed) and asks for the total weight in the range from l to r. In other words, for each query, compute:

\( S = \sum_{i=l}^{r} w_i \)

Efficiently process the queries using the prefix sum technique.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two space-separated integers n (the number of coins) and q (the number of queries).
2. The second line contains n space-separated integers representing the weights of the coins.
3. The following q lines each contain two space-separated integers l and r, representing a query asking for the total weight from the l-th coin to the r-th coin.

outputFormat

For each query, output the sum of the weights in the specified range on a separate line to stdout.

## sample

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

13
13
17

</p>