It is 14^th of Feb, Chotu has worked really hard for the past seven days to impress his crush. Now it's time to take her on a perfect date. He has planned to take his girl to LoveLand. LoveLand is a mystical place built only for new lovers. LoveLand is a one dimensional world of N blocks numbered from 1 to N, the i^th block has a fare Ai that the couple has to pay for visiting the block.

Chotu being a student has limited pocket-money left for the date. In this hard time he is asking for your help. Don't worry, you don't have to lend him money instead he will ask you certain question to verify if he has enough money for the date. Each query comprises of two integers L and R, denoting two block numbers in the LoveLand. You have to tell Chotu what is the total cost of visiting the blocks [L, L + 1, L+2,....R] (both inclusive).

Chotu is pretty impatient for the date, so you have to be really quick in answering all his queries.
Input

First line contains integer N and Q denoting number of blocks and the number of queries respectively.
Next line contains N integers denoting the fare of visiting each block.
Q lines follow each with two integers L and R.
Ouptut

For each query print the required answer.
Constraints

1 ≤ N ≤ 10^5

0 ≤ Ai ≤ 10^4

1 ≤ Q ≤ 10^5

1 ≤ L ≤ R ≤ N

SAMPLE INPUT
7 4
1 2 3 4 5 6 7
1 1
2 5
1 7
4 6

SAMPLE OUTPUT
1
14
28
15

见题面

见题面