Playlist Duration Queries

You are given a playlist with N songs, each with a known duration, and Q queries. Each query consists of two integers L and R asking for the total duration of songs from position L to R (inclusive).

Your task is to process each query efficiently by precomputing prefix sums. This will allow you to answer each query in constant time.

The mathematical formulation for the duration between indices L and R is:

$$duration = prefix[R] - prefix[L-1]$$

where prefix[i] is the cumulative sum of song durations up to the ith song.

inputFormat

The first line of input contains two integers N and Q separated by a space, representing the number of songs and the number of queries respectively.

The second line contains N integers separated by spaces indicating the duration of each song.

The following Q lines each contain two integers L and R (1-indexed) representing the starting and ending positions for the query.

All input is provided via stdin.

outputFormat

For each query, output a single integer on a new line representing the total duration of the songs between indices L and R (inclusive).

Output should be written to stdout.

## sample

5 3
300 150 200 400 250
1 3
2 5
1 5

650
1000
1300

</p>