题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，再给定 $m$ 个询问。每个询问给出两个整数 $x$ 和 $y$（$1 \le x \le y \le n$），请你求出 $a_x + a_{x+1} + \cdots + a_y$ 的值。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，用空格隔开。

接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示一个询问。

输出格式

对于每个询问，输出一行一个整数，表示该区间内元素的和。

样例

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

15
5
4

样例解释

• 第一个询问 1 5：$1+2+3+4+5=15$。
• 第二个询问 2 3：$2+3=5$。
• 第三个询问 4 4：仅第 $4$ 个元素，结果为 $4$。

数据范围与提示

• $1 \le n \le 10^6$，$1 \le m \le 10^4$。
• 数组中每个元素及所有区间和均在 int 类型取值范围内。
• $1 \le x \le y \le n$。