题目描述

给定一个长度为 $n$ 的整数数组 $a[1..n]$，以及 $m$ 次区间查询。每次查询给出一对下标 $(l, r)$，要求你输出数组 $a$ 在区间 $[l, r]$ 上的元素之和。数组和在任何时刻均保证不会溢出 64 位有符号整数。数组内容在查询过程中不会发生修改。

输入格式

n m
a_1 a_2 … a_n
q_1_l q_1_r
q_2_l q_2_r
…
q_m_l q_m_r

• 第一行包含两个整数 $n, m$，分别表示数组长度和查询次数。（$1 \le n, m \le 10^5$）
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示原始数组内容。保证 $|a_i|\le10^9$，累计区间和在 $\pm2^{63}$ 范围内。
• 接下来 $m$ 行，每行两个整数 $l, r$，表示一次区间求和查询。保证 $1 \le l \le r \le n$。

输出格式

输出 $m$ 行，每行输出一个整数，表示对应查询区间 $[l, r]$ 上的元素之和。

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

2
8
11
-2

解释：

• 查询 1: 区间 $[1,3]$ 的和 $=3+1+(-2)=2$；
• 查询 2: 区间 $[2,5]$ 的和 $=1+(-2)+5+4=8$；
• 查询 3: 区间 $[1,5]$ 的和 $=3+1-2+5+4=11$；
• 查询 4: 区间 $[3,3]$ 的和 $=-2$。