题目描述

在遥远的森林里有 $N$ 个光头强，第 $i$ 个光头强的光头指数为 $A_i$。

现在灰太狼想知道从第 $a$ 个光头强到第 $b$ 个光头强的光头指数之和为多少。

灰太狼好奇心很强，会问你许多这样的 $a,b$ 区间。

输入格式

第一行是两个整数 $N$ 和 $M$，分别表示光头强的个数以及灰太狼想知道的区间个数。

接下来一行有 $N$ 个整数，第 $i$ 个整数 $A_i$ 代表 第 $i$ 个光头强的光头指数。

接下来 $M$ 行每行有两个整数 $a,b$，代表灰太郎的询问区间。

输出格式

对每个询问，输出相应的结果。

样例

4 4
1 3 5 7
1 1
1 4
2 3
3 4

1
16
8
12

数据范围

对 $30\%$ 的数据，$1≤N,M≤2000$。

对全部数据，$1≤N,M≤2×10^5,1≤A_i≤10^9,1≤a≤b≤N$。