#include <bits/stdc++.h>
using namespace std;
struct node{
int s,e,m;
long long mx,sm;
node *l,*r;
node(int S,int E){
s=S;e=E;m=(s+e)/2;mx=sm=0;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int x,long long nv){
if(s==e){mx=nv;sm=nv;return;}
if(x<=m)l->upd(x,nv);
else r->upd(x,nv);
mx=max(l->mx,r->mx);
sm=l->sm+r->sm;
}
long long mq(int x,int y){
if(s==x&&e==y)return mx;
if(y<=m)return l->mq(x,y);
if(x>m)return r->mq(x,y);
return max(l->mq(x,m),r->mq(m+1,y));
}
long long sq(int x,int y){
if(s==x&&e==y)return sm;
if(y<=m)return l->sq(x,y);
if(x>m)return r->sq(x,y);
return l->sq(x,m)+r->sq(m+1,y);
}
}*root=new node(0,200005);
int main(){
int n,q;
scanf("%d%d",&n,&q);
if(n<=200&&q<=200){
long long arr[n+5][n];
for(int i=0;i<n;i++)scanf("%lld",&arr[0][i]);
for(int i=1;i<=n;i++){
arr[i][0]=arr[i-1][0];
for(int j=1;j<n;j++){
arr[i][j]=max(arr[i-1][j-1],arr[i-1][j]);
}
}
int t,l,r;
for(int i=0;i<q;i++){
scanf("%d%d%d",&t,&l,&r);l--;r--;
long long ans=0;
for(int j=l;j<=r;j++){
ans+=arr[t][j];
}
printf("%lld\n",ans);
}
}else{
long long arr[n];
for(int i=0;i<n;i++){
scanf("%lld",&arr[i]);
root->upd(i,arr[i]);
}
int t[q],l[q],r[q]; bool st2=1,st3=1;
for(int i=0;i<q;i++){
scanf("%d%d%d",&t[i],&l[i],&r[i]);
if(t[i]!=t[0])st2=0;
if(l[i]!=r[i])st3=0;
}
if(st2){
for(int i=n-1;i>=0;i--){
root->upd(i,root->mq(max(0,i-t[0]),i));
}
for(int i=0;i<q;i++){
printf("%lld\n",root->sq(max(0,l[i]-1),r[i]-1));
}
}else if(st3){
for(int i=0;i<q;i++){
printf("%lld\n",root->mq(max(0,l[i]-1-t[i]),max(0,l[i]-1)));
}
}
}
}
