题目描述

输入一个长度为$n$的数组，询问$m$次区间和 $n$个数组元素$a_i$ 求$m$次询问中 每个区间内的元素和

输入格式

第一行两个整数$n,m$，表示数组长度和询问次数。 接下来第二行，$n$个整数$a_i$，表示数组的元素。 接下来$m$行，每行两个整数$l,r$，表示区间的左端点和右端点。

输出格式

$m$行区间和的结果。

样例

3 2
1 3 2
1 3
2 2

6
3

提示

$1\le n \le100000,1\le m \le100,0\le ai \le1000$