题目描述

现有编号从 $1\sim n$ 的数列，有 $m$ 次询问，每次询问区间 $[l,r]$ 的所有元素之和。

输入格式

第一行两个整数 $n,m$ ，表示数列元素的数量和询问次数；

第二行 $n$ 个整数 $a_i$ ，表示每个数列元素的值；

接下来的 $m$ 行，每行两个整数 $l,r$ ，表示每次询问的区间。

输出格式

输出 $m$ 行，每行输出该次询问的区间元素之和。

样例输入

6 4
5 2 6 3 1 9
2 6
1 5
3 4
1 6

样例输出

21
17
9
26

数据范围

对于 $30\%$ 的数据：$0<l,r\le n,m\le 100$ ；

对于 $100\%$ 的数据： $0<l,r\le n,m\le 100000,1 \le a_i \le 100$ 。