训练记录的区间求和

出题组把连续 n 天的训练积分变化记为 a₁, a₂, …, aₙ。积分变化可以为负数。 负责人提出 q 次询问，每次给出 l 和 r，需要知道第 l 天到第 r 天（包含两端）的积分变化总和。 记录在所有询问期间不会修改。

输入格式

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

第二行包含 n 个整数 a₁, a₂, …, aₙ。

接下来 q 行，每行包含两个整数 l 和 r，表示一次询问。天数从 1 开始编号。

输出格式

输出 q 行，第 i 行为第 i 次询问的区间和。

数据范围

• 1 ≤ n, q ≤ 200000。
• −10^9 ≤ aᵢ ≤ 10^9。
• 每次询问均满足 1 ≤ l ≤ r ≤ n。
• 区间和的绝对值不超过 2×10^14，应使用 64 位有符号整数。
• 时间限制 2000 ms，内存限制 256 MiB。

样例输入

5 4
3 -2 7 0 -5
1 3
2 5
4 4
1 5

样例输出

8
0
0
3

样例解释

第一次询问为 3−2+7=8。第二次为 −2+7+0−5=0。第三次只包含第 4 天。 不同询问可以重叠，也可以完全相同。