#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
ll t,l,r,i;
bool operator<(const obj &o) const{
return t<o.t;
}
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,q;
cin >> n >> q;
vector<ll> a(n);
for(ll &i : a) cin >> i;
vector<obj> qs(q);
for(ll i = 0;i<q;i++){
qs[i].i = i;
cin >> qs[i].t >> qs[i].l >> qs[i].r;
}
sort(qs.begin(),qs.end());
vector<ll> ans(q);
vector<ll> b(n+1,0);
for(ll i = 0;i<n;i++) b[i+1] = a[i]+b[i];
ll t = 0;
for(obj o : qs){
ll dt = o.t-t;
if(dt){
deque<pair<ll,ll>> q;
for(ll i = 0;i<n;i++){
while(q.size()&&q.front().second<i-dt) q.pop_front();
while(q.size()&&q.back().first<=a[i]) q.pop_back();
q.push_back({a[i],i});
a[i] = q.front().first;
}
for(ll i = 0;i<n;i++) b[i+1] = a[i]+b[i];
t = o.t;
}
//for(ll i = 0;i<n;i++) cout << a[i] << " \n"[i+1==n];
ans[o.i] = b[o.r]-b[o.l-1];
}
for(ll i : ans) cout << i << "\n";
}
