【题目描述】

众所周知，狮均国内吼叫总值（RealGDS perlion）是衡量一个狮子国狮子 健康程度的重要指标。其计算方法为，选取若干只狮子，将每个狮子吼叫的次数 相加的总值。 叶子是狮子国健康委员会的会长，有人举报小林汇报的狮均国内吼叫总值的 数据有误，所以他想请你帮忙计算。 具体来说，你会知道编号为 1 到 n 的 n 只狮子吼叫的次数 。叶子会提出 q 个问题。对于每个问题它会给出 l 和 r。它想知道编号在 l 和 r 之间的狮子的狮均国内吼叫总值。

【输入格式】

第一行2个整数 n，q，代表狮子的数量和叶子的问题数。n，q≤10^5

第二行 n 个整数 ，代表编号为 i 的狮子的吼叫次数。 第3到第 3+q 行，每行两个整数 l, r（ 1 ≤ l ≤r ≤ n）

【输出格式】

q 行整数，代表计算出来的狮均国内吼叫总值。