小蓝 同学有着很强的计算能力,张老师为了检验 小蓝 同学的计算能力,写了一个n个数的数列。张老师问了小蓝 同学 m 个问题,每个问题都是请 小蓝 同学计算这个数列从第x个数开始到第y个数结束这个区间的所有数的和。请你编程计算出结果。
第一行包含两个整数n和 m。第二行包含n个整数。接下来 m行,每行包含两个整数x和y表示。
共m行,每行输出一个询问的结果。
样例输入1
6 3 1 3 6 5 4 2 1 3 2 5 3 6
样例输出1
10 18 17
【数据范围】1≤x≤y≤n1≤n,m≤100000−1000≤数列中元素的值≤1000