Problem 1 — Range Sum Queries (easy)

Statement. Given an array of n integers and q queries. Each query gives l r (1-indexed). Output the sum of a[l..r].

Input

n q
a1 a2 ... an
q lines: l r

Output For each query print the sum on its own line.

Constaints

• 1 ≤ n, q ≤ 2e5
• |ai| ≤ 1e9 (use 64-bit sums)
• 1 ≤ l ≤ r ≤ n

Sample Input:

5 2
1 2 3 4 5
1 3
2 5

Output:

6
14