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.</p>

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 H_i (1 <= H_i <= 1,000). He has an additional Q (1 <= Q <= 500) queries -- each query is a pair of integers S_j and E_j (1 <= S_j <= E_j <= 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 S_j..E_j (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: H_i
• Lines N+2..N+Q+1: Line j+N+1 describes query j with a pair of integers: S_j and E_j
</ul>

 

출력 형식

• Lines 1..Q: Line j of the output file contains a single integer that is the sum of the hay bale counts for days S_j through E_j
</ul>

 

예제 입력

4 2
5
8
12
6
1 3
2 4

예제 출력

25
26

힌트

Days:      1 2  3  4 
Counts:    5 8 12  6

query 1..3:  5 + 8 + 12 = 25
query 2..4:  8 + 12 + 6 = 26