题目描述

给定大家一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$。

接下来有 $q$ 次询问，每次询问给定 $l,r$，请你输出 $a_l \sim a_r$ 之间的和。

数据范围:

所有测试点满足 $1≤n,q≤10^5$，$1≤l≤r≤n$，$1≤a_i≤10^9$。

输入格式

第一行一个整数 $n,q$，表示数组长度和询问次数。

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

最后 $q$ 行，每行两个整数 $l,r$，表示查询范围。

输出格式

输出 $q$ 行，每行一个整数，表示 $a_l \sim a_r$ 之间的和。

5 2
1 2 3 4 5
3 5
1 5

12
15

提示