输入一个长度为 $n$ 的整数序列。

接下来再输入 $m$ 个询问，每个询问输入一对 $l, r$。

对于每个询问，输出原序列中从第 $l$ 个数到第 $r$ 个数的和。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一个询问的区间范围。

输出格式

共 $m$ 行，每行输出一个询问的结果。

数据范围

$1 \le l \le r \le n$,
$1 \le n,m \le 100000$,
$-1000 \le 数列中元素的值 \le 1000$

输入样例：

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

输出样例：

3
6
10

已生成 25 组前缀和区间求和测试数据（1.in/1.out ... 25.in/25.out），包含 n/m 上限压力、负数、全 0、只查边界、超大输出等。

下载测试数据（zip）

下面按 1..25 逐组说明每组主要在卡哪些常见错误做法（正确：预处理前缀和 pre[i]=a1+...+ai，回答 sum(l,r)=pre[r]-pre[l-1]；注意 1-based 询问；用 64 位存前缀和/答案）：

1. 样例：基础正确性。

2. n=1 且为负数：卡边界、负数处理（别把负数当 0）。

3. 全 0：卡输出恒 0；也卡有人用累加但初始化/下标错导致非 0。

4. 小随机 + 查询覆盖两端/全段/中段：卡 l=1、r=n、以及一般区间计算。

5. 递增正数：卡公式正确性（容易人工校验），也卡整型累加别溢出小类型。

6. 正负交错：卡负数参与前缀和，很多错法会“只会正数”。

7. ±1000 交替：卡前缀和正负频繁变化，容易暴露 “pre 写成 abs/取 max” 之类怪错。

8. 全 1（专门卡 off-by-one）：(1,n),(2,n),(1,n-1) 等，卡 pre[r]-pre[l] 写错、或 l-1 处理错。

9. n 很小(10) 但 m=10000 很大：卡 O(nm) 暴力每次遍历区间会慢；必须 O(1) 查询。

10. n=100000 很大但 m 很小：卡只建前缀和一次；也卡读入/数组开大是否正确。

11. n=100000 全 1000，m=20000 随机区间：卡大数据性能 + 大和；也卡 32 位溢出风险。

12. n=100000 全 -1000，m=20000 随机区间：同 #11 但全负，卡符号与溢出。

13. n=1000，查询每个单点 (i,i)：卡单点区间、以及 l=r 情况。

14. n=1000，固定长度重叠区间：卡大量重叠区间时的正确性（暴露 “每次从 0 重新算” 的慢做法）。

15. n=100000 全 1000，m=1000 全是 (1,n)：卡超大答案（1e8 级别），要求 64 位（很多人用 int 也许还行，但容易在别的构造下炸；这里同时卡重复输出）。

16. n=100000 全 -1000，m=1000 全是 (1,n)：同 #15 但全负，卡符号。

17. n=100000 随机，m=20000 短区间（长度≤50）：卡大量小区间查询（暴力仍会慢），也卡边界 r=min(n, l+len)。

18. n=100000 随机，m=20000 长区间（随机 l,r）：卡一般性正确性与性能。

19. a[i]=(-1)^i * i（数值随 i 增大且正负交错）：卡前缀和幅度增大时的正确性（容易溢出小类型/写错符号）。

20. n=100000 全 0，m=20000 随机区间：强卡任何“没有初始化/脏数据”的错误（应全 0）。

21. n=2 极小但 m=20000：卡极端小 n 下的下标边界（l-1=0 的处理），以及高频查询。

22. 周期数组（每 3 个一个 1000，其余 -999）+ 对齐区间：卡周期性导致前缀和不单调，暴露“以为单调可二分/错误优化”。

23. n=100000 随机，查询全是 l=1：卡 l=1 特殊情况（pre[0] 必须是 0）。

24. n=100000 随机，查询全是 r=n：卡 r=n 边界，数组大小/前缀最后一位别越界。

25. 最大输出压力：n=100000 全 1000，m=100000，查询 (1,i)：

    • 强卡 I/O（输出 100000 行）
    • 强卡前缀下标与性能（必须 O(n+m)）
    • 卡溢出（结果最大到 1000*100000=1e8，但前缀用 64 位最稳）

你继续下一题的话，我也会同样：给 zip + 每组数据对应卡点逐条说明。