Range Sums

**Description:** Given n integers and q queries, each query gives indices l and r (1-based). Print the sum a[l] + a[l+1] + ... + a[r] for every query. **Input:** Line 1: n q (1 <= n, q <= 2*10^5). Line 2: n integers (-10^9 <= a_i <= 10^9). Next q lines: l r (1 <= l <= r <= n). **Output:** q lines — the range sums. **Example:** 5 2 / 3 -1 4 1 -5 / 1 3 / 2 5 -> 6 / -1.