Every day Farmer John feeds the cows a lavish meal of premium gourmet hay. He then records the number of bales on the next line of his expense notebook.
When tax time comes, FJ realizes that he neglected to record the dates for the hay feedings. He must calculate a number of different totals of successive hay feedings in order to solve the puzzle of which feedings went with which month of expenses.
FJ has created a dataset with N (4 <= N <= 500) days conveniently numbered 1..N of hay bale counts Hi (1 <= Hi <= 1,000). He has an additional Q (1 <= Q <= 500) queries -- each query is a pair of integers Sj and Ej (1 <= Sj <= Ej <= N) that denote that start and end indices of some hay bale counts.  Your job is to sum the hay bale counts for the days Sj..Ej (inclusive) and report one sum for each query.

* Line 1: Two space-separated integers: N and Q
* Lines 2..N+1: Line i+1 contains a single hay bale count for day i: Hi
* Lines N+2..N+Q+1: Line j+N+1 describes query j with a pair of integers: Sj and Ej

* Lines 1..Q: Line j of the output file contains a single integer that is the sum of the hay bale counts for days Sj through Ej

4 2
5
8
12
6
1 3
2 4

25
26

Four days; two queries.  Bale counts: 5, 8, 12, and 6. Count Days 1..3 and 2..4.
Days:      1 2  3  4
Counts:    5 8 12  6
query 1..3:  5 + 8 + 12 = 25
query 2..4:  8 + 12 + 6 = 26