题目描述

给定一个有$N$个数的数组$A$，这些数按照顺序分别为$A_1,A_2\dots A_n$

有$Q$次询问，每次询问分别给出一个$l$和$r$($l\leq r$)，你需要计算出$\sum^r_{i=l} \ \ A_i$的结果（也就是$A_l + A_{l+1} \dots + A_r$的和）

输入格式

第一行两个正整数 $N$和$Q$，数组$A$的大小和询问次数。

第二行 $n$ 个非负整数，相邻两个数用空格隔开，表示数组 $A_1$, $A_2$, $\cdots$, $A_n$。

第三行到第$Q + 2$行有两个正整数$l$和$r$，表示所有数和的范围

输出格式

每行输出一个非负整数，其中第$i$行表示第$i$次查询的答案。

样例 #1

样例输入 #1

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

样例输出 #1

1
15
9
12
9

提示

数据规模与约定

• 对于 $50\%$ 的数据，保证 $N,Q \leq 2000$。
• 对于 $100\%$ 的数据，保证 $1\leq N,Q\leq 2*10^6$，$0\le A_i\le 10^3$，$l$和$r$都在$N$的范围内。

该题读入量较大，请使用更快的读入方式