#897. 前缀和

前缀和

【模板】前缀和

题目描述

给定一个长度为n的数组a1,a2,....ana_1, a_2,....a_n

接下来有q次查询, 每次查询有两个参数l, r.

对于每个询问, 请输出al+al+1+....+ara_l+a_{l+1}+....+a_r

输入格式

第一行包含两个整数n和q.

第二行包含n个整数, 表示a1,a2,....ana_1, a_2,....a_n

接下来q行,每行包含两个整数 l和r.

输出格式

按照题目意思输出

样例 #1

样例输入 #1

3 2
1 2 4
1 2
2 3

样例输出 #1

3
6

提示

1n,q1051≤n,q≤10^5

109a[i]109−10^9≤a[i]≤10^9

1lrn1≤l≤r≤n