题目描述

给定一个长度为$\red n$的整数序列 $\red {a_1}$ , $\red {a_2}$ ..... $\red {a_n}$ ，接下来有 $\red {m}$ 次询问，每次询问给出一个区间 $\red {[l,r]}$ ,请你回答序列中元素 $\red {a_l}$ 到 $\red {a_r}$ 之间所有的元素之和。

输入格式

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

接下来一行有$\red n$个整数。

接下来$\red m$行，每一行有两个整数$\red l$和$\red r$。

输出格式

对每一次询问输出区间所有元素的和。

样例

输入样例

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

输出样例

3
5
15

数据范围与提示

$\red{1≤n≤1000000}$，$\red{1≤m≤10000}$.

区间中任意一个元素、任意一段区间中所有元素的和不会超过int表示范围。