Book Shelf Queries

You are given a bookshelf consisting of N shelves, where the i-th shelf contains a certain number of books. You need to answer Q queries. In each query, you are given two integers l and r (1-based indices), and you must compute the total number of books on the shelves from l to r inclusive.

To solve the problem efficiently, consider using the prefix sums technique. Let \( S(i) \) denote the total number of books from shelf 1 to shelf \( i \). Then the number of books in the range \( [l, r] \) is given by:

\( \text{result} = S(r) - S(l-1) \),

with the understanding that \( S(0) = 0 \). Use this method to answer each query.

inputFormat

The first line contains two integers N and Q separated by a space.

The second line contains N space-separated integers, representing the number of books on each shelf.

Each of the next Q lines contains two space-separated integers l and r indicating the range of shelves for the query.

outputFormat

For each query, output a single line containing the total number of books in the specified shelf range.

## sample

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

12
16
3

</p>