Background

Special for beginners, ^_^

Description

徐老师正在给同学们讲解区间求和问题。 他在黑板上写下了一列整数，并提出了一个问题： “从第 $l$ 个数到第 $r$ 个数，它们的和是多少？”

聪明的同学们发现，如果直接每次都去把区间的数加一遍，可能会非常慢，特别是当数据很多、问题也很多的时候。 于是，徐老师希望你写一个高效的程序，帮他快速计算出这些区间的和。

Format

输入：

• 第一行包含两个整数 $n,q$ $(1 \leq n,q \leq 10^5)$，分别表示数组长度和询问个数。
• 第二行包含 $n$ 个整数 $(|a_i| \leq 10^5)$，表示数组的元素。
• 接下来 $q$ 行，每行两个整数 $l,r$ $(1 \leq l \leq r \leq n)$，表示一个区间。

输出：

• 对每个询问输出一个整数，表示区间和。

Sample

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

6
14
4