该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

圣魔法学院格勒佛利斯要分班了！ 你们作为瑾洛菲校长的得力助手，当然要尽一份力啦。

题目描述

校长将会给你们长度为 $n$ 的序列 $a$ ，$a_i$ 表示第$i$个班级的人数。 以及 $q$ 次询问 $l$ 与 $r$ 。
$Q(l, r)= a_l + a_{l+1} + ··· + a_{r-1} + a_r$。
请你告诉校长每一次询问的 $Q(l, r)$ 。

输入格式

第一行，两个整数 $n、q$，用空格隔开。
第二行，$n$ 个整数表示序列 $a$ 。
接下来$q$行，每行两个整数 $l,r$ 表示一次询问 $Q(l,r)$ 。

输出格式

$q$ 行，每行一个整数表示每次询问的答案。

输入输出样例 #1

输入 #1

4 2
4 3 2 1
1 4
2 3

输出 #1

10
5

【数据范围】

对于30%的数据：$1≤n≤q≤10000$
对于100%的数据：$1≤n≤q≤7000000$