输入$n$个数，给出$m$个询问，询问区间[$x,y$]的和。

输入

第一行为$n$和$m$，$1 \leq n,m \leq 100000$

接下来一行为$n$个数，范围在$0$ ~ $100000$之间

接下来$m$行，每行两个数$x,y$，输出第$x$个数到第$y$个数之间所有数的和。保证$x \leq y$

输出

$m$个输出

样例

样例输入1

5 3
1 2 0 7 6
1 3
2 2
4 5

样例输出1

3
2
13