Description

你需要维护 N 个整数组成的序列，支持 Q 次询问，每次询问区间 [l,r] 的数字之和是多少.

Input

第一行两个整数 N，Q.
接下来一行 N 个数字，表示序列的初始值是多少.
接下来 Q 行，每行两个整数 l , r.

Output

输出 Q 行，每行一个整数，代表对应区间的元素之和.

Sample Input

5 2
1 2 3 4 5
1 3
3 5

Sample Output

6
12

Hint

0<=N,Q<=100000,a[i]<=1e9
常数尽量小吧，要不很容易被卡.