题目描述

小A有\(n\)张纸牌，每一张纸牌上都有一个数字\(a_i\)。现在他将这些纸牌进行编号，从\(1\)开始到\(n\)，并需要知道从第\(l\)张纸牌到第\(r\)张纸牌的数字和是多少？由于数据量太大，于是他找到了你来帮他解决这个问题，你能帮他解决吗？

输入格式

第一行，包含两个整数\(n\)和\(q(1≤n,q≤10^5)\)，分别表示序列的长度和查询的次数。

第二行包含\(n\)个整数\(a_1,a_2,a_3……a_n\)，表示纸牌上的数。

接下来\(q\)行，每行包含两个整数\(l\)和\(r\)，表示一次查询的区间。

输出格式

输出\(q\)行，每行一个整数，表示对应查询的结果。

样例数据

输入样例

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

输出样例

11
6
-2

【样例解释】

• 第一次查询：\(1+3+(−2)+5+4=11\)
• 第二次查询：3\(+(−2)+5=6\)
• 第三次查询：\(−2\)

【数据范围】

• 对于\(50\)%的数据，\(n,q≤1000\)。
• 对于\(100\)%的数据，\(n,q≤10^5\)

【来源】

kobelukuankuan2025CSP-J模拟赛T1