题目描述

前缀和的技巧，必须要建立和熟练运用，这道题就是前缀和的基础应用。

陶陶学了数组以后，他对数组之间的累加和特别感兴趣，于是他就提出了要求 数组 元素之间的累加和的问题。

例如：现在有长度为 10 的数组： 3 2 5 1 4 5 3 7 8 2

从第2个元素到 第 5个元素的和就是 2+5+1+4=12

从第4个元素到第9个元素的和就是 1+4+5+3+7+8=28

输入格式

第一行 n k 两个正整数,分别表示 数组有n个元素,k次求和查询 (0<=n,k<=100000)

第二行为n个整数 数组的n个元素

以下有k行,每行两个元素,为求和的起点和终点

输出格式

k行,每行为起点到终点的和.

样例

input

10 2
3 2 5 1 4 5 3 7 8 2
2 5
4 9

output

12
28

限制与提示

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$