题目背景

数据较弱，不是很建议做

临近 CSP 复赛，hyclol 的教练让他学了亿些算法（真的就亿点）。当然，以 hyclol 的智商是一下子记不住的，so.....

题目描述

hyclol 的教练看 hyclol 记不住，所以打算给 ta 恶补一下，具体是这样的：教练把那 $n$ 个算法从左到右排成一排，编号为 $1$ 到 $n$，每次选择两个数 $l$ 和 $r$（$1\le l \le r \le n$），对于该范围内所有可能的连续子区间 $[x,y]$（$l≤x≤y≤r$），都会给出一道题目让 hyclol 做，这道题目会包含 $x\sim y$ 之间的所有算法。（这确实有点钛令人红温了）

hyclol 对每一个算法的红温程度都进行了评价，分别记为 $a_1 \sim a_n$，而每道题目的红温程度等于该题目所包含的算法的红温程度之和，每次训练的红温程度等于该训练所包含的题目的红温程度之和。

hyclol 偷看了一下教练给 ta 的训练计划，发现上面共有 $m$ 次训练。ta 把每个算法的红温程度和训练计划发给了你，希望你能帮 ta 求出每次训练的红温程度。

输入格式

第一行两个整数 $n,m$ ，意义同上。

第二行 $n$ 个整数，表示序列 $a$.

接下来 $m$ 行每行两个整数 $l,r$，表示一次训练。

输出格式

$m$ 行，分别表示每次训练的红温程度。

3 3
1 2 3
1 3
1 2
2 3

20
6
10

4 6
1 2 3 4
2 4
1 4
2 3
3 4
1 2
1 3

30
50
10
14
6
20

数据规模与约定

$1\le n,m \le 10^5$，$1 \le a_i \le 3 \times 10^2$

保证答案不会爆long long