You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

宝贝有一个小猪储钱罐，每天都会往里面存零花钱，一共存了 n 天，每天存的钱数都是正整数（在 1 到 1000 之间）。 之后妈妈会有 m 个小疑问，都会问：“从第 l 天到第 r 天，一共往储钱罐里存了多少钱呀？”。请你帮宝贝算出每个疑问的答案吧！

输入格式

第一行有两个整数 n 和 m，分别表示宝贝存钱的总天数，以及妈妈的疑问个数。第二行有 n 个正整数，按顺序表示宝贝第 1 天到第 n 天，每天往储钱罐里存的钱数。接下来 m 行，每行有两个整数 l 和 r，表示妈妈的一个疑问：想知道第 l 天到第 r 天的存钱总数。

输出格式

一共输出 m 行，每行一个整数，对应妈妈每个疑问的答案（也就是第 l 天到第 r 天的存钱总数）。

数据说明

（1≤l≤r≤n）；1<=n,m<=100000 ；

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

3
6
10

输入样例说明

宝贝一共存了 5 天，有 3 个疑问； 每天存的钱数：2 元、1 元、3 元、6 元、 4 元； 疑问 1：第 1 天到第 2 天一共存了多少钱？ 疑问 2：第 1 天到第 3 天一共存了多少钱？ 疑问 3：第 2 天到第 4 天一共存了多少钱？

输出样例说明

疑问 1 答案：2 + 1 = 3 元； 疑问 2 答案：2 + 1 + 3 = 6 元； 疑问 3 答案：1 + 3 + 6 = 10 元。