#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int M = 2e5 + 1;
int seg[M*2];
void modify(int p,int x,int v=0,int s=0,int e=M)
{
if (s+1==e)
{
seg[v]=x;
return;
}
int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
if (p<mid)
modify(p,x,lc,s,mid);
else
modify(p,x,rc,mid,e);
seg[v]=max(seg[lc],seg[rc]);
}
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];
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];
ll pre[n+1]={};
for (int i=0;i<n;i++)
cin>>a[i], modify(i,a[i]);
int t;
cin>>t;
for (int i=0;i<n;i++)
a[i]=get(i-t,i+1), pre[i+1]=pre[i]+a[i];
for (int i=0;i<m;i++)
{
if (i) cin>>t;
int l,r;
cin>>l>>r;
cout<<pre[r]-pre[l-1]<<endl;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
int t=1;
// cin>>t;
while (t--)
solve();
return 0;
}
