Range Sum Query (Static)

Problem statement

A finance dashboard answers many requests for the total across a consecutive range of daily changes. The historical values do not change during these queries, making a one-time preprocessing step worthwhile. Your task For each inclusive zero-based range [left, right], return the sum of the array values in that range. Preprocess in O(n), then answer each query in O(1). Important details Both endpoints are included. Negative values reduce the total, and a single-position range returns that value. Use prefix sums with a separate initial zero so that ranges beginning at index zero need no special subtraction case. Worked example For [3, -2, 5], query [0, 2] returns 6 and query [1, 1] returns -2. Each query uses the same unchanged array.

Input format

First line: n q. Next line: n values. Next q lines: left right.

Output format

Print one range sum per line.

Constraints

1 <= n, q <= 10000; -1000000000 <= values <= 1000000000; 0 <= left <= right < n; use 64-bit sums.

Sample input

3 2
3 -2 5
0 2
1 1

Sample output

6
-2