Revenue between two days

Problem

You have the daily revenue for n days, numbered 1 to n. Answer q questions. Each question gives two days l and r, and asks for the total revenue from day l to day r, both included.

Input, output and limits

Input: Line 1: the integers n and q. Line 2: n integers, the revenue of each day. Then q lines, each with two integers l and r.
Output: q lines: the total for each question.
Constraints: 1 ≤ n, q ≤ 2 * 10^5
1 ≤ l ≤ r ≤ n
-10^9 ≤ revenue ≤ 10^9

Examples

Example

Input

Output

13
16
1

The totals are 13, 16 and 1.

Hints

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

Hint 1

Adding up each range separately is O(n) per question, which is too slow when q is large.

Hint 2

Build a list where entry i holds the total of the first i days. Then each question is one subtraction.

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

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More How to Approach a Problem problems

Problem

Input, output and limits

Examples

Hints

More How to Approach a Problem problems