John and William study in same class. John has sharp and fast memory. So In order to challenge him, William decided give him as array of ‘n’ integers and ask him the sum of all the integers in any subsequence of elements between index ‘x’ and ‘y’ (1- indexed) both inclusive. Since you are the best friend of John, help him to answer William’s queries

Input Format

First Line contains two integers ‘n’ and ‘m’, where ‘n’ represents no. of elements in array and ‘m’ represents the no. of queries. Next line contains ‘n’ space separated elements of array Next ‘m’ subsequent lines contains two integers ‘x’ and ‘y’

Output Format

‘m’ lines containing the sum of the subsequences

Constraints

9< n< 1001 4< m< 100 0< x <= y < n+1 0<= Element in the array < 10^9+1