前缀和

题目描述

给一个数列 $a_1, a_2, \dots, a_n$ 和 $m$ 个询问。

每次询问给出两个数 $l, r$，求 $a_l + a_{l+1} + \dots + a_r$ 的值。

输入格式

第一行两个整数 $n, m$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行，每行两个整数 $l, r$。

输出格式

输出 $m$ 行，每行一个整数表示答案。

样例输入

5 5
7 6 4 7 4
2 5
1 3
3 5
1 2
2 4

样例输出

21
17
15
13
17

数据范围

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 10^5, 1\leq a_i\leq 10^9, 1 \le l \le r \le n$。