题目背景

怎么感觉这题好像做过？

众所周知，一年一度的 “篮球杯” 校赛已于 $4$ 天前开赛。约半个月前，科创部将这一消息通知到了各个班的班群里，并积极动员大家参与到比赛中。截止至 $10$ 月 $27$ 日晚 $20$ 点，$2023$ 级一共有 $107$ 名计网er报名了今年的校赛，人数与去年相比有所提升。

这其中就不乏有学习了一年专业课，跃跃欲试想将知识变现的同学们。现在校赛已过，接下来就是省赛了。由于很少参加比较正式的算法竞赛，很多同学不知道省赛会出什么题型，害怕自己在比赛中碰到没学过的东西，而 Dusk 就是其中之一。在完成校赛后，他找 PC 问起了 篮球杯 省赛有没有什么比较常出的典型题。

PC 回想了一下，决定把去年做过最典型且简单的题目改编一下，放到这里。如果你能通过今天的题目，或许明年省赛你就能多掌握一个知识点。

题目描述

本题与题目 Day6_我是篮球杯糕手 唯一的区别在于 $q$ 的范围被增大了。如果你已经完成了那道题目，可以在原先代码的基础上进行更改，想想怎么才能优化算法，处理 $q$ 更大的情况。

为了让 PC 更方便地了解自己的支出情况，请你帮他编写一个小程序。给出 PC 近 $n$ 个月中每个月的总支出，PC 会用你的程序查询 $q$ 次，每次查询的内容为从第 $x$ 个月开始到第 $y$ 个月他的总支出为多少。

输入格式

输入共 $q + 2$ 行。

第 $1$ 行 $2$ 个由空格隔开的整数 $n, q$，代表共有 $n$ 个月的支出数据，以及 $q$ 次查询。

第 $2$ 行 $1$ 个整型数组 $a$， 其中$a_i$，代表第 $i$ 个月的总支出。数字之间由单个空格隔开。

接下来 $q$ 行，每行 $2$ 个整数 $x_j,y_j$，代表第 $j$ 次询问的内容为第 $x_j$ 个月到第 $y_j$ 个月的总支出。

输出格式

输出 $q$ 行，每行 $1$ 个整数 $t_j$，代表从第 $x_j$ 个月开始到第 $y_j$ 个月（闭区间），PC 的总支出为 $t_j=\sum\limits_{i=x_j}^{y_j} a[i]$。

4 3
15 20 25 30
1 4
2 4
1 1

90
75
15

提示

样例中，一共有 $4$ 个月的数据和 $3$ 次询问。其中：

• 第 $1$ 次询问的是第 $1$ 个月到第 $4$ 个月的支出总和，即所有月份的支出总和，为 $15+20+25+30=90$。
• 第 $2$ 次询问的是第 $2$ 个月到第 $4$ 个月的支出总和，为 $20+25+30=75$。
• 第 $3$ 次询问的是第 $1$ 个月到第 $1$ 个月的支出总和，即第 $1$ 个月的支出，为 $15$。

数据规模与约定

对于全部的测试点，保证$1 \leq x_j \leq y_j \leq n \leq 10^5$，$1 \leq q \leq 10^5$，$0 \leq a_i \leq 10^6$。