#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF=0x3f3f3f3f;
const ll oo=0x3f3f3f3f3f3f3f3f;
template<class T>
using vvector = vector<vector<T>>;
int main() {
speed;
int n,q;
cin>>n>>q;
vvector<int> s(n+1,vector<int>(20));
for (int i=1;i<=n;i++) {
cin>>s[i][0];
for (int k=1;k<20;k++) {
if (i<(1<<k)) continue;
s[i][k]=max(s[i][k-1],s[i-(1<<k>>1)][k-1]);
}
}
while (q--) {
int t,l,r;
cin>>t>>l>>r;
t++;
ll ttl=0;
for (int i=l;i<=r;i++) {
int nt=t;
int ni=i;
nt=min(nt,ni);
int ans=0;
for (int k=19;k>=0;k--) {
if (nt&(1<<k)) {
ans=max(ans,s[ni][k]);
ni-=(1<<k);
}
}
ttl+=ans;
}
cout<<ttl<<"\n";
}
}
/*
10 1
3 1 4 1 5 9 2 6 5 3
4 2 2
*/
