小明参加了一个越野比赛，比赛路线中有 nnn 个任务点。比赛说明中给出了每个任务点距离前一个任务点的距离，所有选手会统一从起点出发，按照任务点编号顺序进行徒步比赛。
小明在比赛过程中，有 kkk 次机会可以向组委会询问任意两个任务点（可能不相邻）之间的总距离，从而分配体力，你作为组委会的成员之一要尽快回答他的提问。
输入输出量较大，建议 scanf/printf 进行输入输出。
输入格式
输入包含三部分：
第一部分有一行，为两个空格隔开的整数 n,k,2≤n≤105,1≤k≤106n,k,2≤n≤10^5,1≤k≤10^6n,k,2≤n≤105,1≤k≤106，表示任务点的个数和询问的次数；
第二部分有一行，为 n−1n−1n−1 个用空格隔开的整数，为每个任务点距离前一个任务点的距离，每个数为不超过 10910^9109 的正整数；
第三部分有 kkk 行，每行有两个空格隔开的整a,b,1≤a 输出格式 输出包含 kkk 个空格隔开的整数，为小明每次询问的两个任务点之间的距离 输出时每行末尾的多余空格，不影响答案正确性 要求使用「文件输入输出」的方式解题，输入文件为 hike.in，输出文件为 hike.out 样例输入 4 3 3 5 1 1 2 2 3 3 4 样例输出 3 5 1