该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

输入格式

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

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

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

输出格式

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

样例

输入样例

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

输出样例

3
5
15

数据范围与提示

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

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