P085 一维前缀和

题目描述

给定 n 个整数 a1, \dots, an，处理 q 次询问，每次给出 l, r（1 \le l \le r \le n），输出 al + a{l+1} + \dots + ar。

要求：每次询问 O(1)。

输入格式

第一行 n, q（1 \le n, q \le 10^5）。
第二行 n 个整数 ai（|ai| \le 10^9）。
接下来 q 行，每行 l, r。

输出格式

q 行，每行一个区间和。

样例

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

输出:
15
9
3