题目描述

给定一个数列 $A$，共有 $n$ 个数，进行 $k$ 次查询，每次查询给定区间 $[L,R]$，求解该区间的数列总和。

输入格式

• 第一行：两个整数 $n$ 和 $k$，分别表示数组元素个数和查询次数
• 第二行：$n$ 个整数，表示数组元素
• 接下来 $k$ 行：每行两个整数 $L$ 和 $R$，表示查询的区间

输出格式

输出 $k$ 行，每行一个整数表示对应查询的区间和

样例

输入样例

10 2
3 2 5 1 4 5 3 7 8 2
2 5
4 9

输出样例

12
28