Akib wants to look at an array.

He is reviewing a list of n integers and needs to manage q queries. Each query is about finding the total sum of values within a specific range [a, b] of the provided array.Considering he can't figure this out on his own, he's looking for assistance to correctly compute and present the sum for each query.
 

The first input line has two integers n and q, the number of values and queries respectively.
The second line has n integers x1,x2,…,xn: the array values.

Finally, there are q lines describing the queries. Each line has two integers a and b: what is the sum of values in range [a,b]?

1 ≤ n,q ≤ 2*10^5
1 ≤ xi ≤ 10^9
1 ≤ a ≤ b ≤ n

Print the result of each query.

Input copy	Output copy
8 4 3 2 4 5 1 1 5 3 2 4 5 6 1 8 3 3	11 2 24 4