A Really Simple Task

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

本题题目描述很简单啊(不要有擂台赛的阴影),算法也很简单啊(这次我发4)。给定一个含有N个数的整数序列a{...},各元素的位置编号由1~N,给定Q次查询,对于第j次查询给定一个Lj,Rj求[ Lj , Rj ] 区间内所有元素之和

 

Input

多组输入
对于每组输入第一行有两个整数N,Q( 0 < N,Q < = 10^5 ),分别代表元素的个数和查询次数
第二行有N个整数a1 ~ aN( 0 < = ai < = 1000 ),代表该整数序列
接下来的Q行每行有两个整数Lj , Rj( 1 < = Lj < = Rj < = N ),代表第j次查询要查询的闭区间的左右端点

 

Output

 对于每组输入,输出Q个整数,代表第j次查询的结果,即[Lj,Rj]区间内所有元素之和,每个整数占一行

Sample Input

3 2
2 3 3
1 3
2 2
4 1
2 0 0 0
1 3

Sample Output

8
3
2

Hint

 

Source

Shannon