【模板】前缀和

题目描述

给定一个长度为n的数组$a_1, a_2,....a_n$

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

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

输入格式

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

第二行包含n个整数, 表示$a_1, a_2,....a_n$

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

输出格式

按照题目意思输出

样例 #1

样例输入 #1

3 2
1 2 4
1 2
2 3

样例输出 #1

3
6

提示

$1≤n,q≤10^5$

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

$1≤l≤r≤n$