Background

鄞州区青少年“船过三峡”创意航海模型比赛是鄞州独创的益智航海创意科技项目，从2014年开始创设。已经历8个春秋。“船过三峡”创意航海项目设计是在传统航海模型的基础上增加障碍难度，让选手克服重重困难，激励选手不断改进创新设计，结合实践经验逐步完善自己的设想，以2节五号碱性电池为能源，但方向舵控制方式不能用任何电子装置，让模型船经入口通过3道错位的航道门，三个航道门分别起名瞿塘峡、巫峡、西陵峡，这就是“船过三峡”的由来。

该项目的选手得分由各个环节的得分相加而来。总共有$n（4<=n<=5 0 0）$个环节，裁判老师需要进行$q（1<=q<=5 0 0）$次查询，每次查询给出两个整数$s_i$和$e_i（1<=s_i、e_i<=n）$表示各个环节的索引，请帮忙求出每次查询得到的分数。

Input

第1行：两个空格分隔的整数：$n$和$q$

第2行到$n+1$行：第$i+1$行表示第$i$个环节的得分：$h_i$

第$n+2$行到第$n+q+1$行：用一对整数描述查询区间：$s_i$和$e_i$

Output

第$1$行到$q$行：包含一个整数，它是从$s_i$到$e_i$之间各个环节的得分总和。

Samples

4  2
5
8
12
6
1  3
2  4

25
26

Limitation

从第1环节到第3环节的得分总和5+8+12=25；从第2环节到第4环节的得分总和8+12+6=26