UMR与欧尼酱

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Umaru 今天看到新发售的游戏之后,又耐不住要马上买来惹,然而众所周知 UMR 是干物女,所以她又去烦她的欧尼酱啦,欧尼酱真是拿小埋没办法 (¬_¬),所以只好做出了妥协。
欧尼酱告诉她,我现在给你 N 个数,标号 1 到 N,然后我会进行 M 次询问,对于每次询问我会告诉你一个区间 L,R(L <= R),你只要能在规定的时间内告诉我从第 L 个数到第 R 个数之间所有数的和,我就去给你买╮(╯_╰)╭。

UMR
(小埋:欧尼酱真当我是一个干物女啊)

大家都知道小埋智商超高,你觉得小埋是怎么做的呢,答对了小埋就会送你一个 AC 哦~

Input

输入数据有多组(数据组数不超过 20),到 EOF 结束。
每组输入包含 M+2 行,第一行为两个正整数 N 和 M (1 <= N, M <= 100000)。 
接下来一行 N 个非负整数,每个数不超过 100。
接下来 M 行,每行包含两个数 L, R (1 <= L <= R <= N)。

Output

对于每次询问,给出区间 L~R 的所有整数的和,每个答案占一行。

Sample Input

5 4
1 2 3 4 5
1 2
2 2
1 5
4 5

Sample Output

3
2
15
9

Hint

Source

【2016级ACM集训队第一次选拔赛】UMR