开始: 2022-03-06 15:30:00

2022年3月双周赛(高级班)

结束: 2022-03-06 18:00:00
当前: 2025-0505-3131 12:22:10  类型:OI 状态:已经结束 
P3 : 前缀和与差分-前缀和  
描述

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

接下来再输入 m 个询问,每个询问输入一对整数L,R。

对于每个询问,输出原序列中从第 L个数到第 R个数的和。

输入

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

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

接下来 m 行,每行包含两个整数 L和R,表示一个询问的区间范围。

数据范围

 1≤ L ≤ R ≤ n 
1≤ n , m ≤ 100000,
−1000 ≤ 数列中元素的值 ≤ 1000
 

输出

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

样例

输入

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

输出

3
6
10