时间限制: 1s

内存限制: 256MB

题目描述

老师给了小明一个长度为 $n$ 的数组 $a$，和 $q$ 次询问。

在每次询问中，老师给了两个正整数 $l,r$， 希望小明告诉她数组中第 $l$ 个数到第 $r$ 个数的和是多少。

小明觉得这个问题太难了，于是交给了善于编程的你。

输入格式

第一行两个正整数 $n,q (1 \leq q \leq n \leq 10^6)$ ，分别表示数组 $a$ 的长度，和老师给小明的 $q$ 次询问。

第二行有 $n$ 个正整数，$a_1,a_2,a_3, \cdots ,a_n$，其中每个 $a_i$ 满足 $1 \leq a_i \leq 100$。

接下来的 $q$ 行，每行两个整数 $l,r (1 \leq l \leq r \leq n)$ ，表示一次询问的内容。

输出格式

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

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

6
5
14