#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, ii> query;
struct seg {
int s, e, m, v;
seg *l, *r;
seg(int _s, int _e) {
s = _s, e = _e, m = (s + e) / 2, v = 0;
if (s != e) {
l = new seg(s, m);
r = new seg(m + 1, e);
}
}
void update(int i, int nv) {
if (s != e) {
if (i > m) r -> update(i, nv);
else l -> update(i, nv);
v = max(l -> v, r -> v);
} else v = nv;
}
int query(int a, int b) {
if (s == a && e == b) return v;
if (a > m) return r -> query(a, b);
if (b <= m) return l -> query(a, b);
return max(l -> query(a, m), r -> query(m + 1, b));
}
} *root;
struct Fenwick {
int s;
vector<long long> f;
Fenwick(int N) {
s = N;
f = vector<long long>(s + 1, 0);
}
void update(int i, long long v) {
for (; i <= s; i += i & -i) f[i] += v;
}
long long query(int a) {
long long ans = 0;
for (; a > 0; a -= a & -a) ans += f[a];
return ans;
}
};
int main() {
int N, Q;
scanf("%d %d", &N, &Q);
long long S[N];
int T[Q], L[Q], R[Q];
for (int i = 0; i < N; ++i) scanf("%lld", &S[i]);
map<int, vector<int> > queries;
for (int i = 0; i < Q; ++i) scanf("%d %d %d", &T[i], &L[i], &R[i]);
for (int i = 0; i < Q; ++i) queries[T[i]].push_back(i);
if (queries.size() == 1) {
root = new seg(0, N - 1);
for (int i = 0; i < N; ++i) root -> update(i, S[i]);
for (int i = 0; i < N; ++i) S[i] = root -> query(max(0, i - queries.begin() -> first), i);
for (int i = 1; i < N; ++i) S[i] += S[i - 1];
for (int i = 0; i < Q; ++i) printf("%lld\n", S[R[i] - 1] - (L[i] == 1 ? 0 : S[L[i] - 2]));
} else if (*max_element(S, S + N) <= 2) {
int prev1 = -1, prev2 = -1;
set<query> q;
Fenwick f(N);
for (int i = 0; i < N; ++i) f.update(i + 1, S[i]);
long long ans[Q];
for (int i = 0; i < N; ++i) {
if (S[i] == 0) {
if (prev2 != -1) q.insert(query(ii(i - prev2, -1), ii(2, i + 1)));
else if (prev1 != -1) q.insert(query(ii(i - prev1, -1), ii(1, i + 1)));
} else if (S[i] == 1) {
if (prev2 != -1) q.insert(query(ii(i - prev2, -1), ii(1, i + 1)));
prev1 = i;
} else prev2 = i;
}
for (int i = 0; i < Q; ++i) q.insert(query(ii(T[i], i), ii(L[i], R[i])));
for (query i: q) {
if (i.first.second == -1) f.update(i.second.second, i.second.first);
else ans[i.first.second] = f.query(i.second.second) - f.query(i.second.first - 1);
}
for (int i = 0; i < Q; ++i) printf("%lld\n", ans[i]);
} else {
root = new seg(0, N - 1);
for (int i = 0; i < N; ++i) root -> update(i, S[i]);
for (int i = 0; i < Q; ++i) {
long long ans = 0;
for (int j = L[i] - 1; j < R[i]; ++j) ans += root -> query(max(0, j - T[i]), j);
printf("%lld\n", ans);
}
}
return 0;
}
