#include<bits/stdc++.h>
#define ll long long
#define S second
#define F first
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ll n,q,a,b,t;
cin>>n>>q;
vector<ll>s(n),x(n);
for(ll i=0;i<n;i++){
cin>>s[i];
}
cin>>t>>a>>b;
priority_queue<pair<ll,ll>>mx;
mx.push({s[0],0});
for(ll i=1;i<n;i++){
mx.push({s[i],i});
while(i-mx.top().S>=t+1){
mx.pop();
}
x[i]=mx.top().F;
}
x[0]=s[0];
ll pref[n+5];
pref[0]=0;
for(ll i=0;i<n;i++){
pref[i+1]=pref[i]+x[i];
// cout<<pref[i+1]<<" ";
}
cout<<pref[b]-pref[a-1]<<"\n";
q--;
while(q--){
cin>>t>>a>>b;
if(n<=200 && q<=200){
priority_queue<pair<ll,ll>>mx;
mx.push({s[0],0});
for(ll i=1;i<n;i++){
mx.push({s[i],i});
while(i-mx.top().S>=t+1){
mx.pop();
}
x[i]=mx.top().F;
}
x[0]=s[0];
// for(ll j:x){
// cout<<j<<" ";
// }
pref[0]=0;
for(ll i=0;i<n;i++){
pref[i+1]=pref[i]+x[i];
// cout<<pref[i+1]<<" ";
}
}
a--;
cout<<pref[b]-pref[a]<<"\n";
}
return 0;
}
/*
5 5
9 3 2 6 5
3 2 2
3 1 5
3 3 5
3 2 5
3 2 4
*/
