Audit Window

Problem

A shop keeps a ledger of n daily balance changes. A positive number is money in, and a negative number is money out. An auditor arrives and asks q questions. Each question names two days l and r, and wants the total change from day l to day r, both included. The shop owner would like the answers before the auditor finishes the tea.

Input

The first line has two integers n and q. The second line has n integers a_1 ... a_n. Each of the next q lines has two integers l and r.

Output

For each question print the sum a_l + a_(l+1) + ... + a_r on its own line.

Constraints

• 1 ≤ n, q ≤ 70000
• -10⁹ ≤ a_i ≤ 10⁹
• 1 ≤ l ≤ r ≤ n
• Sums do not fit in 32 bits.

Notes

In the first example the three questions ask for days 1 to 5, days 2 to 3 and day 4 alone. The sums are 4 - 2 + 7 + 1 + 3 = 13, then -2 + 7 = 5, then 1.