C 从零开始的 C 语言生活，决定先从前缀和入手。
为此，他向喵喵提出了一系列问题：
Q: 前缀和是什么？
A: 前缀和可以简单理解为 “数列的前 n 项的和"，是一种重要的预处理方式，能大大降低查询的时间复杂度。
具体的说，对于一个长度为 n 的数组 a 。我们按照 
，构造一个数组 b 。则称数组 b 为数组 a 的前缀和数组。这样构造出来的前缀和数组 b 满足 bn = a1 + a1 + …… + an 。
举个例子，原数组 a = {2, 1, 1, 1, 1} 。则 b0 = a0 = 2 ， b1 = b0 + a1 = 2 + 1 = 3 ， b2 = b1 + a2 = 3 + 1 = 4 ……
以此类推得到 a 的前缀和数组 b = {2, 3, 4, 5, 6} 。
Q: 前缀和有什么性质？
A: 根据前缀和的简单理解，观察数组前缀和 b ，发现前缀和数组 b 满足 bn = a1 + a2 + …… + an 。
于是，我们对原数组 a 简单预处理后，就能够非常快速的得到原数组 a 任意一段区间 [l, r] 的和，即： 
。
以上文求出的 b = {2, 3, 4, 5, 6} 为例，易见 b4 - b2 = 2 = a3 + a4 。
(……)
现在，小 C 已经完全掌握前缀和的用法，兴奋地手舞足蹈，于是喵喵决定出一道题目来检验一下他的学习成果：
根据喵喵的记录，小 C 从零开始到完全掌握前缀和共用了 t 的时间，喵喵同时记录下了每个时间小 C 增加的掌握值。现在喵喵将记录给你，同时给出了 q 次询问，在每次询问中，喵喵想要知道小 C 从时间 [l, r]
t， q ( 1 ≤ t ≤ 105, 1 ≤ q ≤ 105 ) 具体输入含义见题干。
第二行依次输入 t 个整数 a1, a2, ……, at ( 0 ≤ ai ≤ 105 ) ，第 i 个整数代表在时间 i 增加了多少的掌握值。
接下来 q 行，每行输入两个整数 l, r ( 1 ≤ l ≤ r ≤ t )，具体输入含义见题干。
5 2
1 2 3 4 5
1 5
2 4
15
9