题目描述

一辆火车有 $N$ 节车厢，车厢从 $1...n$ 进行编号，每节车厢里都有乘客。第 $i$ 节车厢的乘客数量用 $A_i$ 表示。

对于 $q$ 个询问，每组询问起始车厢编号$left$和结尾车厢编号$right$，求$left$车厢到$right$车厢内的人数总和。

输入格式

第一行两个整数$n$和$q$, 分别代表车厢数量和询问次数

第二行$n$个整数，依次表示从1号车厢到$n$号车厢的人数

接下来的$q$行，每行两个整数$left$和$right$

输出格式

输出$q$行，每行对应一个询问的答案

样例数据

8 2
11 23 21 12 32 19 11 23
2 4
2 5

56
88

数据范围

对于100%的数据，$1 \le n \le 100000, 1\le a_i \le 100, 1\le q \le 100000$，$left$ 和 $right$ 保证在 1~$n$ 范围内且 $left \le right$