#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=start-(start>end);x!=end-(start>end);x+=(start<end?1:-1))
#define all(x) x.begin(),x.end()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a, Args... args) { return max(a,MAX(args...)); }
template<typename... Args>
ll MIN(ll a, Args... args) { return min(a,MIN(args...)); }
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
struct node{
int s,e,m;
long long val=-1;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1;
if (s==e){
val=0; //here the value of all points is 0 at first
}
else{
l=new node(s,m);
r=new node(m+1,e);
val=l->val+r->val; //edit this for diff
}
}
long long query(int i,int j){
if (i==s && j==e) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return max(l->query(i,m),r->query(m+1,j));
}
void update(int i, long long k){
if (s==e){
val=k;
}
else{
if (i<=m) l->update(i,k);
else r->update(i,k);
val=max(l->val,r->val);
}
}
}*root=new node(0,200005);
int n,k;
int arr[200005];
vector<iii> q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
rep(x,1,n+1){
cin>>arr[x];
root->update(x,arr[x]);
}
bool ST2=true,ST3=true;
int a,b,c;
rep(x,0,k){
cin>>a>>b>>c;
if (b!=c) ST3=false;
q.push_back(iii(a,ii(b,c)));
if (q[0].first!=q.back().first) ST2=false;
}
if (n<=200 && k<=200){
for (auto &it:q){
ll ans=0;
rep(x,it.second.first,it.second.second+1){
ans+=root->query(max(0LL,x-it.first),x);
}
cout<<ans<<endl;
}
}
else if (ST3){
for (auto &it:q){
cout<<root->query(max(0LL,it.second.first-it.first),it.second.first)<<endl;
}
}
else if (ST2){
rep(x,1,n+1) arr[x]=root->query(max(0LL,x-q[0].first),x);
rep(x,1,n+1) arr[x]+=arr[x-1];
for (auto &it:q){
cout<<arr[it.second.second]-arr[it.second.first-1]<<endl;
}
}
}
