该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你怎么知道我韵律源点ptt 12.76了.jpg

墨梓柒最近沉迷音游无法自拔，每天都在《韵律源点》的世界里疯狂推分。为了更科学地提高自己的潜力值（ptt），他开始研究各种歌曲的“谱面”（即note序列）。

他将一个谱面简化成了一个长度为 $N$ 的整数序列 $A$，其中第 $i$ 个数 $a_i$ 代表了这首歌曲中第 $i$ 个 note 的理论最高分。想要打出高分，不仅要处理好高难度的段落，也要保证简单的部分不能失误。

现在，墨梓柒想要快速计算出谱面中任意一个连续片段的分数总和，也就是从第 $L$ 个 note 到第 $R$ 个 note 的理论总分。他发现，这已经不是简单的 A+B 问题了，这简直是它的“究极进化”版！由于墨梓柒是菜b，所以他请求你帮帮他。

他将问题抽象为如下模型：

给定一个包含 $N$ 个整数的序列 $A$。接下来会有 $M$ 次询问，每次询问会给出一个区间 $[L, R]$（包含 $L$ 和 $R$）。你需要对于每一次询问，计算出序列 $A$ 中从第 $L$ 个数到第 $R$ 个数的和。

输入格式

输入第一行包含两个正整数 $N$ 和 $M$ ($1 \le N, M \le 5 \times 10^5$)，分别表示谱面中的note数量和询问的次数。

第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 1000$)，表示每个note的理论分数。

接下来 $M$ 行，每行包含两个正整数 $L$ 和 $R$ ($1 \le L \le R \le N$)，表示一次询问的区间。

输出格式

对于每一次询问，输出一行，包含一个整数，表示对应区间的理论总分。

样例

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

6
9
9

限制

Time Limit: 1000ms Memory Limit: 256MB