小C从零开始的C语言生活，决定先从前缀和入手。

为此，他向喵喵提出了一系列问题：

Q:前缀和是什么？

A:前缀和可以简单理解为 “数列的前n项的和"，是一种重要的预处理方式，能大大降低查询的时间复杂度。

具体的说，对于一个长度为n的数组a。我们按照，构造一个数组b。则称数组b为数组a的前缀和数组。这样构造出来的前缀和数组b满足b_n= a₁+ a₁+ …… + a_n。

举个例子，原数组a = {2, 1, 1, 1, 1}。则b₀= a₀= 2，b₁= b₀+ a₁= 2 + 1 = 3，b₂= b₁+ a₂= 3 + 1 = 4……

以此类推得到a的前缀和数组b = {2, 3, 4, 5, 6}。

Q:前缀和有什么性质？

A:根据前缀和的简单理解，观察数组前缀和b，发现前缀和数组b满足b_n= a₁+ a₂+ …… + a_n。

于是，我们对原数组a简单预处理后，就能够非常快速的得到原数组a任意一段区间[l, r]的和，即：。

以上文求出的b = {2, 3, 4, 5, 6}为例，易见b₄- b₂= 2 = a₃+ a₄。

(……)

现在，小C已经完全掌握前缀和的用法，兴奋地手舞足蹈，于是喵喵决定出一道题目来检验一下他的学习成果：

根据喵喵的记录，小C从零开始到完全掌握前缀和共用了t的时间，喵喵同时记录下了每个时间小C增加的掌握值。现在喵喵将记录给你，同时给出了q次询问，在每次询问中，喵喵想要知道小C从时间[l, r]内掌握值增加了多少。

第一行输入两个整数t， q(1≤t≤10⁵, 1≤q≤10⁵) 具体输入含义见题干。

第二行依次输入t个整数a₁, a₂, ……, a_t(0≤a_i≤10⁵) ，第i个整数代表在时间i增加了多少的掌握值。

接下来q行，每行输入两个整数l, r(1≤l≤r≤t)，具体输入含义见题干。

输出多行。

对于每次询问，请在一行输出一个整数，表示答案。

注意数据范围喵~