Description

每天Farmer John都会用一顿奢侈美味的草料大餐喂养奶牛们。然后，他会在他记录开支的笔记本上记录下草料的包数。

缴税时间到来时，Farmer John意识到自己忘记记录草料喂养的日期。他必须计算出许多不同的连续草料喂养的总数，以解决这个涉及一个月饲料开支难题。

Farmer John设立了一个包含被简单编号为 1 至 N 的 N（4 ≤ N ≤ 500）天的干草包数 H_i（1 ≤ H_i ≤ 1000）。他有 Q（1 ≤ Q ≤ 500）次额外查询，每次查询包含整数 S_j 和 E_j（1 ≤ S_j ≤ E_j ≤ N）代表了起始日期。你的任务是，统计 S_j 至 E_j（包含 E_j）期间总共的草料包数并对每一次查询返回一个总数。

Format

Input

第一行，两个空格隔开的整数：N 和 Q；

第二至第 N + 1行，每行包含一个代表第 i 天草料包数的整数：H_i；

第 N + 2 至 N + Q + 1 行，每行包含第 j 次查询的两个整数：S_j 和 E_j。.

Output

Q行，每行包含一个整数，代表天数从 S_j 到 E_j 的草料包数和。

Samples

4 2
5
8
12
6
1 3
2 4

25
26

Limitation

样例一说明：

四天，两次查询。草料包数：5，8，12，和 6。统计日期为 1 至 3 和 2 至 4。

日次：1 2 3 4

包数：5 8 12 6

查询 1 至 3：5 + 8 + 12 = 25

查询 2 至 4：8 + 12 + 6 = 26