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 ~N~ candies, each with a value ~v_i~, the machine must be able to answer queries about his candies, ~Q~ times.

Each query consists of a range ~(1 \le l_i \le r_i \le N)~, you are to find the sum of all the values within the range, inclusive.

Input Specification

The first line will contain the integers ~N~ and ~Q~. ~(1 \le N, Q \le 100\,000)~

The following ~N~ lines will contain the values of each candy.

The next ~Q~ lines after that will consist of the integers ~l_i~ and ~r_i~, 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

5 4
8
10
123
1
999
1 3
2 4
1 5
5 5

Sample Output

141
134
1141
999