Range totals of daily sales

Problem

An online store records its sales (in rupees) for n days. The manager then asks q questions. Each question gives two days l and r and asks for the total sales from day l to day r, both days included.

Print the answer to every question.

Input, output and limits

Input: The first line has two integers n and q. The second line has n integers: the sales for days 1 to n. Each of the next q lines has two integers l and r.
Output: q lines. Line i has one integer: the total sales from day l to day r for question i.
Constraints: 1 ≤ n, q ≤ 10^5
0 ≤ sales ≤ 10^9
1 ≤ l ≤ r ≤ n

Examples

Example

Input

Output

13
15
1

Days 1–3: 4 + 2 + 7 = 13. Days 2–5: 2 + 7 + 1 + 5 = 15. Day 4 alone: 1.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Adding the days again for every question costs up to n steps per question, which is 10^10 steps in the worst case.

Hint 2

Before the questions, build an array where position i holds the total of days 1 to i.

Hint 3

The total of days l to r is the total up to r minus the total up to l − 1.

Hint 4

Make the array one longer than n and keep position 0 as 0, so l = 1 needs no special case. Use long.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sum & Hashing problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sum & Hashing problems