A. 游戏之神的提问

内存限制:256 MiB 时间限制:1000 ms 输入文件: yx.in 输出文件: yx.out
题目类型:传统 评测方式:文本比较

题目描述

一天,在宿舍睡觉的你,突然梦到了游戏之神,他说:去玩《极限脱出》吧,这部作品的剧情和世界观绝对会带来很大的震撼,值得一玩。

对了,这部作品的第一代发布在nds上,所以要想在电脑上玩,你需要游戏模拟器:推荐desmume,也可以选择nogba,前者虽然优化差一些,但自带了模拟器的即使存档功能,且可以全屏。

但由于你没有吃安利,游戏之神很愤怒(这么好的游戏不玩,暴殄天物啊!),决定对你进行惩罚。

现在,游戏之神给了你 n 个非负整数,分别记为第 1 个数字至第 n 个数字,游戏之神还会向你提出 q 个问题,询问你第 f 个数到第 t 个数之间所有数字的和,请你正确回答游戏之神的所有提问,否则你以后打游戏必掉线。

输入格式

输入的第一行包含两个整数 n,q ,含义如题面所示;

第二行包含 n 个非负整数,每个数字均不超过 10^9

下面 q 行,每行包括两个数字 f,t ,含义如题面所示。

输出格式

对于这 q 行中的每一行,请你输出一个数字,回答游戏之神的提问。

样例

Input

9 4
1 3 4 6 2 5 1000000000 1000000000 1000000000
1 6
7 9
3 5
4 4

Output

21
3000000000
12
6

数据范围与提示

1≤n,q≤10^5

1≤f≤t≤n