题目描述

图书馆记录了连续 $n$ 天每天的图书借阅数量。管理员想了解一些时间段内总共借出了多少本书。他列出了若干个想要了解的时间段，请你帮他计算出每个时间段的总借阅量。

输入格式

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

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天的借阅量。

接下来 $q$ 行，每行两个整数 $l, r$，表示管理员想了解从第 $l$ 天到第 $r$ 天的总借阅量。

输出格式

输出 $q$ 行，每行一个整数，表示对应时间段的总借阅量。

样例输入

7 3
12 8 15 20 10 5 18
1 3
2 5
4 7

样例输出

35
53
53

数据范围

$1 \le n, q \le 10^5$，$1 \le a_i \le 1000$。