题目描述

小明连续 $n$ 天去菜市场买菜，第 $i$ 天花费 $a_i$ 元。妈妈问了 $q$ 个问题，每个问题想知道从第 $l$ 天到第 $r$ 天（含）一共花了多少钱。

输入格式

第一行两个整数 $n, q$。
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$。
接下来 $q$ 行，每行两个整数 $l, r$。

输出格式

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

样例

输入

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

输出

6
9
15

数据范围

• 对于 $30\%$ 的数据：$n, q \le 100$；
• 对于 $100\%$ 的数据：$1 \le l \le r \le n \le 2 \times 10^5$，$1 \le a_i \le 1000$。