Problem C: Caculate The Sum

Problem C: Caculate The Sum

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 444  Solved: 69
[Submit] [Status] [Web Board] [Creator:]

Description

WYQ是个很热心的学姐,她想把自己所学的知识都教给你们。WYQ学姐很喜欢数组,所以争抢着要给你们讲数组的知识,现在要考核你们一个简单的数组的查询知识,WYQ学姐相信你们连数组排序这么难的知识都学会了,这个查询应该是个小case!。现在WYQ学姐给你一个长度为n的数组序列(a1,a2,a3...an),她今天不想排序了,只有m次查询,每次查询有a,b两个数字,让你求下标从ab 的数组序列的和。

Input

第一行输入两个数nmn<=1000000,m<=100000

然后n个数字ai0<=ai,ai<=100000000

然后m行查询,每行两个数字a,b(1 <= a <= b <= n)

Output

对于每次查询,输出下标从a到b的序列的和Sn

Sample Input Copy

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

Sample Output Copy

15
5
10