Description

There were n rows of seats in the classroom. Each row of seats littered with a_i unit of trash. 

For example: first row contained a₁ unit of trash

The janitor wanted to know how many units of trash were littered among row l to row r?

For example: If janitor ask you about row l = 3 to row r = 6. You should answer a₃ + a₄ + a₅ + a₆ unit of trash.

There will be q queries, help janitor  find out the answer so janitor  can clean up the class room.

Note that because janitor  is furious about picking up trash, each number will be follow by a symbol " (/`A`)/ ~I__I " without quotation mark and then there is a blank to separate from the next number.

Note that if you use a loop to get the sum of a_l ~ a_r at each query you will get an Time limit exceed. 

You can use prefix sum to solve this problem

Input

input contains several lines.

First line contains two integer n(1 <= n <= 10⁶), q(1 <= q <= 10⁵) -- the number of rows and the number of queries.

Second line contains n integer a₁ ~ a_n (0 <= a_i <= 10⁹), and each interger followed by a symbol " (/`A`)/ ~I__I " and then there is a blank to separate from the next number.

The following q lines each lines contains two integers l, r ( 1 <= l <= r <= n )

Output

output contain q lines, to each query output the sum of a_l ~ a_r. remember to print \n at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss