Abhishek aka Princu the prince likes arrays a lot. He saw Shakti playing with an array and wanted to play too. Shakti denied borrowing the array to him. He said Abhishek must pass L.F.A.T. (Love For Array Test) to play with the array. Princu after working hard day and night for the test started giving the test. The problem where he is stuck is to find the sum of a range in the array. While solving this question he thought to write a program to efficiently calculate this to impress Shakti. Help him write the program.

INPUT

The first line contains two integers N and Q denoting the size of array and number of queries.

The next N lines contain a value V, where ith line denotes the ith value of the array.

The next Q lines contain two integers L and R, denoting the range.

OUTPUT

For each Query print the sum of array in the range L and R in a new line.

CONSTRAINTS

1 <= N <= 10^6

1 <= Q <= 10^6

1 <= V <= 10^9