Description

输入一个长度为 $n(1 \le n \le 1000)$ 的数组 $a$ ，元素为 $a[1]\cdots .a[n]$ ，之后进行 $m$ 次询问，每次询问给出两个值 $l,r$ （ $r \ge l$ ），求数组： $a[l] + a[l+1] + \cdots .. a[r]$ 的值。

Input Format

第一行 $2$ 个数， $n$ 和 $m$ ，中间用空格分隔（ $1 \le n, m \le 1000)$ 。 之后 $n+m$ 行， 第 $1$ 至 $n$ 行：每行一个数字 $a[i]$ （ $0 \le a[i] \le 1000$ ） 第 $n + 1$ 至 $n + m$ 行：每行 $2$ 个数字 $l, r$ ，中间用空格分隔（ $0 < l \le r \le n$ ）

Output Format

输出共 $m$ 行，每行一个数，对应 $a[l] + a[l+1] + \cdots .. a[r]$ 的值。

3 3
1
3
5
1 2
1 3
2 3

4
9
8

Hint

数据范围

对于 $5\%$ 的数据， $1\le l\le r\le m\le 10$ ， $1\le n\le 10$ ； 对于 $10\%$ 的数据， $1\le l\le r\le m\le 100$ ， $1\le n\le 100$ ； 对于 $100\%$ 的数据， $1\le l\le r\le m\le 1000$ ， $1\le n\le 1000$ ；## 样例说明 例如： $n = 3$ ， $m = 3$ ， $a$ 的元素为 $1, 3, 5$ ，

第 $1$ 个查询为： $1\ 2$ ，对应 $a[1] + a[2] = 1 + 3 = 4$

第 $2$ 个查询为： $1\ 3$ ，对应 $a[1] + a[2] + a[3] = 1 + 3 + 5 = 9$

第 $2$ 个查询为： $2 3$ ，对应 $a[2] + a[3] = 3 + 5 = 8$