2062 - 【基础】周周的越野比赛

周周参加了一个越野比赛,比赛路线中有 n 个任务点。比赛说明中给出了每个任务点距离前一个任务点的距离,所有选手会统一从起点出发,按照任务点编号顺序进行徒步比赛。

周周在比赛过程中,有 k 次机会可以向组委会询问任意两个任务点(可能不相邻)之间的总距离,从而分配体力,你作为组委会的成员之一要尽快回答他的提问。

输入

输入包含三部分:

第一部分有一行,为两个空格隔开的整数 n, k, 2 \leq n \leq 10 ^ 5, 1 \leq k \leq 10 ^ 5,表示任务点的个数和询问的次数; 第二部分有一行,为 n - 1 个用空格隔开的整数,为每个任务点距离前一个任务点的距离,每个数为不超过 10 ^ 9 的正整数; 第三部分有 k 行,每行有两个空格隔开的整数 a, b, 1 \leq a < b \leq n,分别为两个任务点的编号。

输出

输出包含 k 个空格隔开的整数,为周周每次询问的两个任务点之间的距离

样例

输入

4 3
3 5 1
1 2
2 3
3 4

输出

3 5 1

提示

这是一道经典的前缀和的题目,我们只需要将前缀和数组求出,使得 sum[i]中存储起点到 i 的距离即可。

当周周询问 a 点到 b 点的距离时,只需输出 sum[b] - sum[a]

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题