连环询问

题目描述

给定 $n$ 个正整数，请快速回答 $m$ 次连环询问。每次询问会指定一个区间 $[L,R]$，请回答这个区间中所有正整数的和。

输入格式

第一行是正整数 $n$ 和 $m$，用空格隔开。 第二行为 $n$ 个正整数，数字之间用空格隔开。 接下来 $m$ 行，每行两个正整数 $L_i, R_i$，表示一个区间。

输出格式

共 $m$ 行。第 $i$ 行是第 $i$ 次询问的答案。

样例输入 #1

4 2
4 3 2 1
1 4
2 3

样例输出 #1

10
5

数据范围

$1 \le n \le 100000$，$1 \le m \le 1000$，$0 < \text{正整数} \le 10000$，$1 \le L_i \le R_i \le n$。

知识点与难度

本题涉及的知识点从属于 GESP 三级（前缀和、数组应用），难度等级：⭐⭐⭐。

测试点分布