You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

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

例如：现在有长度为 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

Input Format

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

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

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

Output Format

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

Sample

input

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

output

12
28

Hint

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

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