题目描述

小明有一个长度为 $n$ 的数组，小华对这个数组十分好奇，于是他询问小明 $q$ 次，每次询问包含 $l, r$，表示询问 $a_l+a_{l+1}+\ldots+a_r$ 的值，请你帮小明应对每次询问。

输入格式

输入第一行包含两个整数 $n, q$，分别表示数组长度和询问次数。

输入第二包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

此后 $q$ 行，每行包含两个整数 $l,r$ $(1 \leq l \leq r \leq n)$。

输出格式

输出 $q$ 行，每行包含一个整数，代表 $a_l+a_{l+1}+\ldots+a_r$ 的值。

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

3
6
10
15
21
9

数据规模与约定

对于全部的测试点，保证 $1\leq n,q \leq 2\times 10^5$，$1\leq a_i\leq 10^5$。