问题描述

本题为一维前缀和模板。

给定一个长度为 $n$ 的序列 $a$。

再给定 $q$ 组查询，对于每次查询：

给定一对 $l,r$，你需要输出 $\sum_{i=l}^{r} a_i$ 的结果。

输入格式

第一行输入两个正整数 $n,q$。（$1\le n,q \le 10^5$）

第二行输入 $n$ 个正整数 $a_i$。（$1\le i\le n,1\le a_i\le 10^4$）。

接下来 $q$ 行，每行输入 $2$ 个正整数 $l,r$。（$1\le l\le r\le n$）。

输出格式

对于每次查询，输出一行一个整数，表示该次查询的结果。

样例输入

5 3
2 1 3 6 4
1 2
1 3
2 4

样例输出

3
6
10