#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;
vector<ll> s(n+1);
for (int i=1;i<=n;i++) {
cin>>s[i];
}
deque<pii> Q;
vector<pair<pii,int>> qry(q+1);
for (int i=1;i<=q;i++) {
cin>>qry[i].S>>qry[i].F.F>>qry[i].F.S;
}
for (int i=1;i<=n;i++) {
while (!Q.empty() and Q.back().F<=s[i]) Q.pop_back();
Q.push_back({s[i],i});
if (Q.front().S<i-qry[1].S) Q.pop_front();
s[i]=Q.front().F;
}
for (int i=1;i<=n;i++) s[i]+=s[i-1];
for (int i=1;i<=q;i++) {
cout<<s[qry[i].F.S]-s[qry[i].F.F-1]<<"\n";
}
}
