题目描述

小码哥有一个长度为$n$的序列$a_i$，小码哥会进行$q$次询问，每次询问一个区间$[L,R]$，你需要给出下标在这个区间内，所有$a_i$的和。

输入格式

第一行输入两个整数$n,q$。 第二行输入$n$个整数$a_i$。 接下来$q$行，每行两个整数$L,R$，表示一次询问的区间。

输出格式

输出$q$行，每行输出一个整数，表示对应询问的结果。

样例输入 #1

5 3
3 5 8 7 2
1 5
2 4
2 5

样例输出 #1

25
20
22

说明/提示

对于40%的数据，有$1\leq n,q\leq 10^3$。 对于100%的数据，有$1\leq n,q\leq 10^6,1\leq a_i\leq 10^9$。