梦游仙境

【题目描述】

在Asm.def仍然在与人工智能进行艰苦的斗争时，雪甜甜小公主仍然在亚特兰蒂斯里自娱自乐，她不小心误闯了玛丽奥的世界。

她感觉十分有趣，她闯关到了一行有n个小块上面有傻币的地面（可以看成一个数轴），地面上有许多，假如雪甜甜的起点为l,终点为r,跳跃能力为jump,从左往右跳

针对雪甜甜皇家公主给出的q组询问l,r,jump，你需要计算他获得的傻币数

例如下面这种情况

地面的金币数列:

2    1    4    7    4    1    2    5    1

w[1]   w[2]  w[3]  w[4]  w[5]  w[6]  w[7]  w[8]  w[9]

若l=2,r=7,jump=3,则总傻币数为w[2]+w[5]=5（w[8]不算，因为雪甜甜跳不到）

若l=3,r=4,jump=2,则总傻币数为w[3]=4(没法跳，只能留在原地)

【输入格式】

第一行为两个整数n，q

第二行n个数，表示w[i]

接下来q行每行三个数l,r,jump

【输出格式】

总共q行，每行一个答案ans

【样例输入】

【样例输出】

2
7
29
10
4

【提示】

对于30%的数据,n<=2000

对于100%的数据,n<=100000,q<=500000

【来源】