#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int M = 1e5 + 1;
pair<int,int> seg[M*2];
int lz[M*2];
void push(int v,int lc,int rc)
{
seg[lc].first+=lz[v], seg[lc].second+=lz[v];
seg[rc].first+=lz[v], seg[rc].second+=lz[v];
lz[v]=0;
}
void modify(int l,int r,int x,int v=0,int s=0,int e=M)
{
if (s>=r or e<=l) return;
if (l<=s && e<=r)
{
seg[v].first+=x, seg[v].second+=x;
lz[v]+=x;
return;
}
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
push(v,lc,rc);
modify(l,r,x,lc,s,mid);
modify(l,r,x,rc,mid,e);
seg[v].first=max(seg[lc].first,seg[rc].first);
seg[v].second=min(seg[lc].second,seg[rc].second);
}
int get(int l,int r,int v=0,int s=0,int e=M)
{
if (l>=e or r<=s) return 0;
if (l<=s && e<=r) return seg[v].first;
int mid=(s+e)/2, lc=v+1,rc=v+(mid-s)*2;
return max(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}
void solve()
{
int n,m;
cin>>n>>m;
if (max(n,m)<=200)
{
int a[n];
for (int i=0;i<n;i++)
cin>>a[i];
while (m--)
{
int t, l, r;
cin>>t>>l>>r;l--;
ll ans=0;
for (int i=l;i<r;i++)
{
int mx=a[i];
for (int j=i-1;j>=max(0,i-t);j--)
mx=max(mx,a[j]);
ans+=mx;
}
cout<<ans<<endl;
}
}
else
{
int a[n];
for (int i=0;i<n;i++)
cin>>a[i], modify(i,i+1,a[i]);
while (m--)
{
int t,l,r;
cin>>t>>l>>r;
cout<<get(max(0,l-1-t),l).first<<endl;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
int t=1;
// cin>>t;
while (t--)
solve();
return 0;
}
