提示

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

题目描述

陶陶学了数组以后，他对数组之间的累加和特别感兴趣，于是他就提出了要求 数组 元素之间的累加和的问题。 例如：现在有长度为 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}$