Description

You manage a neighborhood library. You are given an array of daily visitor counts, and librarians repeatedly ask "how many people came from day l to day r?" dozens of times a day. Re-summing from the start for every question is too slow. By precomputing a prefix sum array, you can answer any range with a single subtraction.

Input

Output

Constraints

• •1 <= array length N <= 100,000
• •0 <= each visitor count <= 10,000
• •1 <= number of queries Q <= 100,000
• •0 <= l <= r <= N-1

Examples

visitors = [5, 8, 6, 3, 7, 9, 4], queries = [[2, 5], [0, 2], [4, 6]]

[25, 19, 20]

visitors = [10, 0, 4, 6], queries = [[0, 3], [1, 1]]

[20, 0]