当前没有测试数据。

描述

给定一个长度为 n 的整数数组 nums。

接下来有 m 次询问，每次询问给出两个整数 l 和 r，请输出数组中从第 l 个元素到第 r 个元素的和。

数组下标从 1 开始。

格式

输入

第一行两个整数 n 和 m，分别表示数组长度和询问次数。

接下来 n 行，每行一个整数，表示数组 nums 中的元素。

接下来 m 行，每行两个整数 l 和 r，表示一次区间求和询问。

输出

对于每次询问，输出一行答案，表示 nums[l] + nums[l + 1] + ... + nums[r] 的值。

示例

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

6
14
4

4 2
-1
3
5
2
1 4
2 3

9
8

数据约定

• $1 \le n \le 10^5$
• $1 \le m \le 10^5$
• $-10^9 \le nums[i] \le 10^9$
• $1 \le l \le r \le n$