P024 区间求和（前缀和）

题目描述

给定一个长度为 n 的数组 a，有 q 次询问。每次询问给出 l, r（1 \le l \le r \le n），输出 al + a{l+1} + \dots + ar。

输入格式

第一行 n, q。
第二行 n 个整数。
接下来 q 行，每行 l, r。

输出格式

每行一个整数。

样例

输入:
5 3
1 2 3 4 5
1 3
2 4
1 5

输出:
6
9
15