题目描述

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，以及 $q$ 次询问。

每次询问给出 $l,r$，请回答 $\sum\limits_{i=l}^{r}a_i$。

输入格式

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

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，每行两个整数 $l,r$，保证 $1\le l\le r\le n$。

输出格式

输出 $q$ 行，每行一个整数表示对应询问的答案。

输入输出样例 #1

输入 #1

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

输出 #1

6
14
4

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le q\le 10^5$，$|a_i|\le 10^9$。