背景故事（趣味）


幻兽帕鲁守护着一条由n个能量石环组成的能量链。每个能量石上记录了一个整数能量值。帕鲁会不断接到m个查询，问某一段能量石上的能量总和是多少。你要在能量链静态（不有更新）的情况下高效回答所有查询，否则帕鲁会因等待太久生气把你变成小草！


给定长度为n的整数数组a[1..n]，随后给出m个查询，每个查询为一对整数l, r（1 ≤ l ≤ r ≤ n），要求输出区间和a[l] + a[l+1] + ... + a[r]。

第一行：两个整数 n ,m
第二行：n 个整数 a1 a2 ... an
接下来 m 行：每行两个整数 l r（表示一个查询）
约束
1 ≤ n ≤ 10000
1 ≤ m ≤ 10000
|ai| ≤ 10^9

对每个查询输出一行，表示对应区间的和（使用 64 位整数类型）。

查询 1..3：1+2+(-1)=2
查询 2..5：2+(-1)+4+3=8
查询 3..3：-1
查询 1..5：1+2-1+4+3=9