时间限制：1秒　　内存限制：256M

---

【题目描述】

　　每天农场主约翰都会用一顿奢侈美味的草料大餐喂养奶牛们。然后，他会在他记录开支的笔记本上记录下草料的包数。 缴税时间到来时，约翰意识到自己忘记记录草料喂养的日期。他必须计算出许多不同的连续草料喂养的总数，以解决这个涉及一个月饲料 开支难题。

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

【输入格式】

　　行 \(1\): 两个空格隔开的整数: \(N\) 和 \(Q\)
　　行 \(2..N+1\): 行 \(i+1\) 包含一个代表第 \(i\) 天草料包数的整数: \(H_i\)
　　行 \(N+2..N+Q+1\): 行 \(j+N+1\) 包含第 \(j\) 次查询的两个整数: \(S_j\) 和 \(E_j\)

【输出格式】

　　行 \(1..Q\): 行 \(j\) 包含一个整数代表天数从 \(S_j\) 到 \(E_j\) 的草料包数和。

【输入输出样例】

　Input

4 2
5
8
12
6
1 3
2 4

　Output

25
26

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤500\)，\(1≤H_i≤500\)，\(1 ≤ Q ≤ 500\)。

【来源】

　　Mr.he