背景

模板题

题目描述

有一个长为 $n$ 的序列A，其中序列A中的每个数 $0 \leq A_i \leq 1000$，现有 $m$ 次查找，每次求区间 $[L,R]$ 之间所有数的和。

格式

输入

第一行两个整数 $n$ 和 $m$，范围 $1\leq n,m\leq 10^5$ 。

第二行， $n$ 个空格隔开的数。

第 $3$ 到 $m +2$ 行，每行两个数，表示此次查询的 $L$ 和 $R$ （$1 \leq L \leq R \leq n$）。

输出

$m$ 行，每行一个数， 区间 $[L,R]$ 每个数 的和。

样例

5 2
1 2 3 4 5
1 5
2 4

15
9

测试限制

每个测试点均为 1s, 128MB .