#include <bits/stdc++.h>
using namespace std;
long long S[200005];
int T[200005];
int L[200005];
int R[200005];
long long ans[200005];
long long val[(1<<20)+5];
long long lazyadd[(1<<20)+5];
int N;
long long prefixSum[1000005];
inline int left1(int x){
return (x<<1)+1;
}
inline int right1(int x){
return (x<<1)+2;
}
void init(int i = 0, int s = 1, int e = N){
int m = (s+e)>>1;
lazyadd[i] = 0;
if(s == e){
val[i] = S[s];
}else{
int l = left1(i);
int r = right1(i);
init(l, s, m);
init(r, m+1, e);
val[i] = max(val[l], val[r]);
}
}
long long rmq(int x, int y, int i = 0, int s = 1, int e = N){
int m = (s+e)>>1;
if(x <= s && e <= y){
return val[i];
}
int l = left1(i);
int r = right1(i);
if(x > m){
return rmq(x, y, r, m+1, e);
}else if(y <= m){
return rmq(x, y, l, s, m);
}else{
return max(rmq(x, y, r, m+1, e), rmq(x, y, l, s, m));
}
}
int main(){
int Q;
scanf("%d%d", &N, &Q);
for(int i = 1; i <= N; i ++){
scanf("%d", &S[i]);
}
for(int i = 0; i < Q; i ++){
scanf("%d%d%d", &T[i], &L[i], &R[i]);
}
init();
prefixSum[0] = 0;
for(int i = 1; i <= N; i ++){
prefixSum[i] = prefixSum[i-1] + rmq(max(i-T[0],1), i);
}
for(int i = 0; i < Q; i ++){
int t = T[i];
int l = L[i];
int r = R[i];
if(t == T[0]){
printf("%lld\n", prefixSum[r]-prefixSum[l-1]);
continue;
}
long long ans = 0;
for(int j = l; j <= r; j ++){
//printf("%d ", rmq(max(j-t, 1), j));
ans += rmq(max(j-t, 1), j);
}
//printf("\n");
printf("%lld\n", ans);
}
}
