销售额统计

故事背景

一家书店记录了连续 n 天的日销售额。月底盘点时，经理需要频繁查询“从第 l 天到第 r 天的总销售额是多少”。如果每次都把区间内的数字逐个相加，工作会非常低效。请你写程序帮经理快速完成多次区间和查询。

题目描述

给定一个长度为 n 的整数数组 a，需要回答 q 次询问。每次询问给出区间 [l, r]（1 ≤ l ≤ r ≤ n），请输出该区间内元素之和。

输入格式

第一行包含两个整数 n、q，表示数组长度与询问次数。 第二行包含 n 个整数，表示数组 a 的元素。 接下来 q 行，每行包含两个整数 l、r，表示一次区间询问（1 基）。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

6
14
15

样例解释 #1

三个区间分别为 [1,3]、[2,5]、[1,5]，其和依次为 1+2+3=6、2+3+4+5=14、1+2+3+4+5=15。

说明/提示

• 数据范围：1 ≤ n, q ≤ 2×10^5；-10^9 ≤ a_i ≤ 10^9。
• 建议使用 64 位整数类型（如 C++ 的 long long）保存和。
• 提示：先构建前缀和 s，令 s[i] 表示前 i 个数之和（s[0]=0），则区间 [l, r] 的和为 s[r]-s[l-1]。