题目背景

翻译自 CSES-1646 题。

题目描述

给定一个包含 $n$ 个整数的数组，你的任务是处理 $q$ 个查询，每个查询形式为：求区间 $[a,b]$ 中的值的和。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示数组中的值的数量和查询的数量。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$：表示数组中的值。

接下来有 $q$ 行，每行包含两个整数 $a$ 和 $b$：表示查询区间 $[a,b]$，要求计算该区间内的元素和。

输出格式

对每个查询，输出区间 $[a,b]$ 的元素和。

样例

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

11
2
24
4

数据范围

• $1 \le n,q \le 2 \cdot 10^5$
• $1 \le x_i \le 10^9$
• $1 \le a, b \le n$