该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 n（n<10000）的数列，求出m个区间[x,y]的数字之和，区间[x,y]的数字指的是从第x个位置到第y个位置范围内的数字，请编程作答。

输入

第一行，输入两个数字 n 和 m,表示数列的长度和区间的个数

第二行，输入 n 个数字，表示数列的元素

接下来m行，每行输入两个整数 x 和 y，表示区间的范围

输出

区间[x,y]的数字之和，每个结果换行输出

样例

5 2
99 1 3 2 1
2 4
2 5

6
7

Limitation

对于 100% 的数据： -2147483648 <= a~i~ <=2147483647