After going out to trick or treat, Adam's plan for getting candies has worked wonderfully! Now he has an abundance of candies, but needs a machine to count these candies. Being very picky, he wants the machine to be able to answer queries about his candies.
Given candies, each with a value , the machine must be able to answer queries about his candies, times.
Each query consists of a range , you are to find the sum of all the values within the range, inclusive.
Input Specification
The first line will contain the integers and .
The following lines will contain the values of each candy.
The next lines after that will consist of the integers and , the leftmost and rightmost index of each query.
Output Specification
For each query, output the sum of the values on a separate line.
Sample Input
Copy
5 4
8
10
123
1
999
1 3
2 4
1 5
5 5
Sample Output
Copy
141
134
1141
999
Comments