背景

flying正在备战🏀杯，每天都坚持刷题。为了跟踪自己的进度，他记录了每天完成的题目数量。

描述

给定 flying 在 $n$ 天内的刷题记录 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 $i$ 天完成的题目数量。

现在有 $q$ 次询问，每次询问给定两个整数 $L, R$，请你回答第 $L$ 天到第 $R$ 天 flying 一共刷了多少题。

输入格式

第一行包含两个整数 $n, q$，分别表示天数与询问次数。

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

接下来 $q$ 行，每行两个整数 $L, R$，表示一次询问。

输出格式

共 $q$ 行，每行一个整数，表示对应询问的区间和。

样例

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

6
14
15

限制

• 对于 $30\%$ 的数据，$n, q \le 1000$
• 对于 $100\%$ 的数据，$n, q \le 10^5$，$1 \le a_i \le 10^4$，$1 \le L \le R \le n$