题目描述

一次训练共有 $n$ 次测评，第 $i$ 次测评得分为 $a_i$。老师会提出 $q$ 个区间查询，每次询问第 $l$ 次到第 $r$ 次测评的总分。

请依次回答所有查询。

输入格式

第一行输入两个整数 $n,q$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行输入两个整数 $l,r$，表示一次区间查询。

输出格式

对于每个查询输出一行，表示 $a_l+a_{l+1}+\cdots+a_r$。

样例

5 3
2 7 1 8 2
1 3
2 5
4 4

10
18
8

数据规模与约定

• $1\le n,q\le 2\times 10^5$；
• $-10^9\le a_i\le 10^9$；
• $1\le l\le r\le n$。

答案可能超过 int 范围，请使用 long long。