38 - 一维前缀和

wlxsq有n个数字,编号从1n,对应a_1,a_2,…,a_n.

现在有m次询问,每次询问输入一个区间[l,r]之间的所有元素的和。

即每次询问 求:a_l+a_{l+1}+…+a_r的和

输入

第一行输入两个整数n,m。

第二行输入n个整数a_i.

接下来输入m行,每行输入两个整数l,r.

输出

对于每一次询问,输出其对应的区间和

样例

输入

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

输出

15
9
12
2

提示

提示

C/C++选手请使用scanf,printf输入输出~

数据规模

50 \% 的数据,满足 1≤n,m≤1000;

100 \%的数据,满足 1≤n,m≤100000,a_iint类型数据

时间限制 3 秒
内存限制 128 MB
讨论 统计
上一题 下一题