区间求和

题目描述

给定整数数组，多次询问连续区间内元素的和。

输入格式

第一行 n、q；第二行 n 个整数；接下来 q 行每行 l、r。

输出格式

每次询问输出一行从 l 到 r 的和（含端点）。

数据范围

1≤n,q≤100000；-10^9≤a_i≤10^9；1≤l≤r≤n。

样例

3 48
-628578479 -244410293 444868027
2 2
1 2
3 3
1 2
2 3
2 2
2 3
2 2
3 3
1 3
3 3
3 3
1 3
1 1
1 1
1 2
2 2
3 3
1 2
3 3
3 3
3 3
1 3
2 2
2 3
3 3
3 3
1 3
3 3
3 3
3 3
3 3
3 3
3 3
1 1
2 2
3 3
1 2
2 2
1 1
3 3
1 2
1 3
1 2
2 2
2 3
3 3
2 2

-244410293
-872988772
444868027
-872988772
200457734
-244410293
200457734
-244410293
444868027
-428120745
444868027
444868027
-428120745
-628578479
-628578479
-872988772
-244410293
444868027
-872988772
444868027
444868027
444868027
-428120745
-244410293
200457734
444868027
444868027
-428120745
444868027
444868027
444868027
444868027
444868027
444868027
-628578479
-244410293
444868027
-872988772
-244410293
-628578479
444868027
-872988772
-428120745
-872988772
-244410293
200457734
444868027
-244410293

7 53
290541511 637802145 790873577 -699621016 -486332110 513048393 -418045073
6 6
7 7
1 5
6 7
7 7
2 6
3 4
7 7
5 7
6 6
4 7
3 3
7 7
6 6
7 7
3 5
4 4
4 5
1 3
7 7
1 5
1 3
6 7
2 5
3 7
4 6
6 7
3 3
7 7
3 4
4 4
6 6
5 5
7 7
2 7
2 3
6 7
1 1
5 6
2 2
2 5
3 6
2 5
5 5
7 7
4 7
7 7
2 3
5 6
2 3
2 7
2 2
7 7

513048393
-418045073
533264107
95003320
-418045073
755770989
91252561
-418045073
-391328790
513048393
-1090949806
790873577
-418045073
513048393
-418045073
-395079549
-699621016
-1185953126
1719217233
-418045073
533264107
1719217233
95003320
242722596
-300076229
-672904733
95003320
790873577
-418045073
91252561
-699621016
513048393
-486332110
-418045073
337725916
1428675722
95003320
290541511
26716283
637802145
242722596
117968844
242722596
-486332110
-418045073
-1090949806
-418045073
1428675722
26716283
1428675722
337725916
637802145
-418045073

说明

所有题目均为标准输入、标准输出；不需要文件读写。函数专题的函数签名是教学要求，普通 OJ 仅能依据程序输出来评测。