题目描述

小 J 需要实现一个可以快速求数列区间和的程序，你也来试试吧！

输入格式

第一行输入两个正整数 $n(1\le n \le 10^6)$ 和 $m(1\le m \le 10^6)$。

第二行连续输入 $n$ 个 $int$ 型整数，用 1 个空格隔开。

接着连续 $m$ 行，每行两个正整数 $x,y$，用 1 个空格隔开，表示一次询问，$[x,y]$ 区间内的元素和是多少。

输出格式

输出共 $m$ 行，每行 1 个整数，表示该数列在对应区间 $[x,y]$ 范围内的元素之和（保证在long long 的范围内）。

输入输出样例

5 3
9 1 2 0 6
2 4
1 3
2 5

3
12
9

说明/提示

我们以后会经常遇到区间，外面的方括号代表包含端点的闭区间，圆括号代表不包含端点的开区间，如：

$[2,5]$ 表示 $2，3，4，5$；

$[2,5)$ 则表示 $2，3，4$。