#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SEG{
private:
	int n;
	vector<int> node;
public:
	SEG(int N){
		n = 1;
		while(n < N) n *= 2;
		node.resize(2*n+1);
	}
	void add(int i, int x){
		for(i++;i<=n;i+=i&-i) node[i] += x;
	}
	int f_(int i){
		int ans = 0;
		for(;i>0;i-=i&-i) ans += node[i];
		return ans;
	}
	int f(int l, int r){
		return f_(r)-f_(l);
	}
};
signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	srand((unsigned)time(NULL));
	int N,Q;
	cin>>N>>Q;
	vector<pair<int,int>> I(N);
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		I[i] = {a,i};
	}
	sort(I.begin(),I.end());
	vector<int> L(Q), R(Q), K(Q), AC(Q), WA(Q);
	for(int i=0;i<Q;i++){
		cin>>L[i]>>R[i]>>K[i];
		L[i]--;
		AC[i] = -1; // -1 個選んでいる状態では <= K
		WA[i] = N+1; // N+1 個は選べないので
	}
	int pb = 18;
	vector<int> Ans(Q);
	while(pb--){
		SEG segk(N), segc(N); // kosuu cost
		vector<vector<int>> Ls(N+1);
		for(int i=0;i<Q;i++) Ls[(AC[i]+WA[i])/2].push_back(i);
		for(int i=0;i<=N;i++){
			for(int pl:Ls[i]){
				int k = segk.f(L[pl],R[pl]);
				if(k <= K[pl]){
					AC[pl] = i;
					Ans[pl] = segc.f(L[pl],R[pl]);
				}
				else WA[pl] = i;
			}
			if(i == N) continue;
			auto [c,p] = I[i];
			segk.add(p,1);
			segc.add(p,c);
			//for(int j=0;j<N;j++) cout<<segc.f(j,j+1)<<' ';
			//cout<<endl;
		}
	}
	for(int x:Ans) cout<<x<<endl;
}