题目描述

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

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

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

【输入格式】

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

第2行~第N+1行：第i+1行包含一个代表第i天草料包数的整数:H_i。

第N+2行~第N+Q+1行：第j+N+1行包含第j次查询的两个整数:S_j 和 E_j。

【输出格式】

共Q行：每行一个正整数，表示每次查询的结果。

4 2
5
8
12
6
1 3
2 4
（输入说明：
四天; 两次查询。草料包数: 5, 8, 12, 6。统计日期1~3和2~4。）

25
26
（输出说明：
日次:    1 2  3  4
包数:    5 8 12  6
查询 1~3天:  5 + 8 + 12 = 25
查询 2~4天:  8 + 12 + 6 = 26 。）