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

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

输入输出量较大，建议 scanf/printf 进行输入输出。

输入格式

输入包含三部分：

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

输出格式

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

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 hike.in，输出文件为 hike.out

样例输入

4 3
3 5 1
1 2
2 3
3 4

样例输出

3 5 1