#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define cerr if(false) cerr
#define watch(x) cerr << (#x) << " is " << (x) << endl;
#define endl '\n'
#define ld long double
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(x) (x).begin(), (x).end()
const int maxn = 200500;
int n, q;
int a[maxn];
int seg[4*maxn];
void upd( int pos, int val, int ind, int cl, int cr) {
if(cl > cr) return;
if(cl == cr) {
// cerr << "setting " << ind << " to " << val << endl;
seg[ind] = val;
} else {
int cm = (cl+cr)/2;
if(pos <= cm) {
upd(pos, val, 2*ind, cl, cm);
} else {
upd(pos, val, 2*ind+1, cm+1, cr);
}
seg[ind] = max(seg[2*ind], seg[2*ind+1]);
}
}
int query(int l, int r, int ind, int cl, int cr) {
if(cl > cr) return -1e18;
if(l > r) return -1e18;
if(cl == l and cr == r) {
return seg[ind];
}
int cm = (cl+cr)/2;
return max(query(l, min(cm, r), 2*ind, cl, cm),
query(max(l, cm+1), r, 2*ind+1, cm+1, cr));
}
int t[maxn], l[maxn], r[maxn];
int psa[maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
upd(i, a[i], 1, 1, n);
}
set<int> S;
for(int i = 1; i <= q; i++) {
cin >> t[i] >> l[i] >> r[i];
S.emplace(t[i]);
}
if(sz(S) == 1) {
int k = *S.begin();
for(int i = 1; i <= n; i++) {
psa[i] = query(max(1LL, i-k), i, 1, 1, n);
psa[i] += psa[i-1];
}
for(int i = 1; i <= q; i++) {
cout << psa[r[i]]-psa[l[i]-1] << endl;
}
} else {
for(int i = 1; i <= q; i++) {
watch(t[i])
int ans = 0;
for(int j = l[i]; j <= r[i]; j++) {
int val = query(max(1LL, j-t[i]), j, 1, 1, n);
cerr << j << " is " << val << endl;
cerr << "quried " << max(1LL, j-t[i]) << "," << j << endl;
ans += val;
}
cout << ans << endl;
}
}
}
/*
Did you read the bounds?
Did you make typos?
Are there edge cases (N=1?)
Are segay sizes proper?
Integer overflow?
DS reset properly between test cases?
Is using long longs causing TLE?
Are you using floating points?
*/
