#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
using namespace std;
vector<ll> seg;
vector<ll> vec;
void build(int l,int r,int ind){
if(l==r){
seg[ind]=vec[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ind*2);
build(mid+1,r,ind*2+1);
seg[ind]=max(seg[ind*2],seg[ind*2+1]);
}
ll query(int l,int r,int start,int end,int ind){
if(r<start||end<l) return 0;
if(start<=l&&r<=end) return seg[ind];
int mid=(l+r)>>1;
return max(query(l,mid,start,end,ind*2),query(mid+1,r,start,end,ind*2+1));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,q;
cin>>n>>q;
vector<ll> f(n+1);
seg.resize(4*n+4);
for(int i=0;i<n;i++) cin>>f[i+1];
vec.resize(n+1);
for(int i=1;i<=n;i++) vec[i]=f[i];
build(1,n,1);
vector<ll> pre(n+1);
int a,b,c;
cin>>a>>b>>c;
for(int i=1;i<=n;i++){
pre[i]=query(1,n,max(1,i-a),i,1);
}
for(int i=2;i<=n;i++) pre[i]+=pre[i-1];
cout<<pre[c]-pre[b-1]<<"\n";
for(int i=1;i<q;i++){
cin>>a>>b>>c;
cout<<pre[c]-pre[b-1]<<"\n";
}
}
