Description

给出$n$个整数$a[1],a[2],...,a[n]$ .

$q$ 次查询，每次查询给出两个整数$l,r$ ，要求输出$\sum_{i=l}^{r}a[i]$ .

Format

Input

第一行有两个正整数，$n$ 表示数组长度，$q$ 表示询问次数.

第二行有$n$ 个整数$a[1],a[2],...,a[n]$ .

接下来$q$行，每行有两个整数$l,r$ 表示查询$\sum_{i=l}^{r}a[i]$ .

. $1\le n,a[i],q\le 10^5$.

.$1\le l \le r\le n$.

Output

对于每组询问输出一个整数代表$\sum_{i=l}^{r}a[i]$ 的值.

Samples

5 2
1 4 2 3 1
1 2
3 5

5
6