#333. 求和

某人热爱数据结构。为了展示他的热爱，并不失风度，他在黑板上写下这样一个式子：

他徐徐解释道：今天的问题是，给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，有 $q$ 次询问，每次询问指定一个区间 $[L,R]$，求

第一行包含两个正整数 $n,q(1 \le n,q \le 2021)$，表示序列的长度和询问的组数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i (|a_i| \le 10^9)$。

接下来 $q$ 行，每行包含两个整数 $L,R$，表示一次询问。

对于每次询问，输出一行，代表询问的答案。

样例输入

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

样例输出

4
7
10
22
35