区间和

题目描述

给定一个长度为 $n$ 的整数数组 $a$。进行 $q$ 次询问，每次给出 $l$ 和 $r$，求 $a_l + a_{l+1} + \dots + a_r$。

输入格式

第一行两个整数 $n$ 和 $q$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行两个整数 $l$ 和 $r$。

输出格式

输出 $q$ 行，每行一个整数，表示对应区间的和。

样例

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

6
14
4

数据范围

$1 \le n, q \le 2 \times 10^5$，$|a_i| \le 10^9$，$1 \le l \le r \le n$。