题目描述

给出一个长度为n的数组a，求数组a某个区间[L, R]之间的元素和为多少。

输入格式

第一行两个数字，n表示数组的长度，m表示要进行的操作次数(1≤m, n≤10^5)；

第二行包括n个整数ai(-10^3≤ai≤10^3)；

后面m行，每行包括两个数L，R(1≤L≤R≤10^5)，表示操作的数组区间。

输出格式

一共m行，每行一个整数，表示对应的区间元素和。

输入/输出样例

10 4
5 2 -3 1 -5 10 150 300 1200 93
1 3
2 5
1 8
1 10

4
-5
460
1753

说明/提示

时间1000ms，内存256MiB