区间求和

题目描述

给定一个长度为 $n$ 的数组 $a$，有 $q$ 次询问，每次询问下标 $l$ 到 $r$（包含两端）之间所有元素的和。

输入格式

第一行两个整数 $n$ 和 $q$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行两个整数 $l$ 和 $r$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示区间和。

样例

5 3
1 2 3 4 5
1 3
2 5
4 4

6
14
4

数据范围

$1 \le n, q \le 10^5$，$|a_i| \le 10^9$，$1 \le l \le r \le n$。

提示：区间和可能超过 int 的范围。