#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) begin(a),end(a)
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(T x:a)out<<x<<',';
	return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=3.5e4+10,M=2,V=N;
const ll INF=1e18,Inf=1e12;
int n,m,a[N];
vector<ll>t[N<<2][M][M],s[N<<2][M][M];
void chkmax(vector<ll>&A,vector<ll>&P,vector<ll>&Q){
	int len=P.size()+Q.size()-1;
	vector<ll>B(len);
	merge(P.begin()+1,P.end(),Q.begin()+1,Q.end(),B.begin()+1,greater<ll>());
	B[0]=P[0]+Q[0];
	for(int i=1;i<len;i++)B[i]+=B[i-1];
	if(A.size()<len)A.resize(len,-Inf);
	for(int i=0;i<len;i++)A[i]=max(A[i],B[i]);
}
void calc(int rt){
	for(int i=0;i<M;i++){
		for(int j=0;j<M;j++){
			auto &s=::s[rt][i][j],&f=t[rt][i][j]=s;
			for(int i=f.size()-1;i;i--)f[i]-=f[i-1];
		}
	}
}
void build(int l=1,int r=n,int rt=1){
	if(l==r){
		s[rt][0][0]={0};
		s[rt][0][1]={-Inf,a[l]};
		s[rt][1][0]={0};
		s[rt][1][1]={a[l],a[l]};
		return calc(rt);
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	for(int i=0;i<M;i++){
		for(int j=0;j<M;j++){
			for(int k=0;k<M;k++){
				chkmax(s[rt][i][j],t[rt<<1][i][k],t[rt<<1|1][k][j]);
			}
		}
	}
	calc(rt);
	for(int i=0;i<M;i++){
		for(int j=0;j<M;j++){
			debug(ary(a,l,r),i,j,s[rt][i][j]);
		}
	}
}
using node=complex<ll>;
bool cmp(const node &a,const node &b){
	return real(a)^real(b)?real(a)<real(b):imag(a)<imag(b);
}
using matrix=array<array<node,M>,M>;
matrix operator * (const matrix &a,const matrix &b){
	static matrix c;
	for(int i=0;i<M;i++){
		fill(c[i].begin(),c[i].end(),node(-INF,0));
	}
	for(int k=0;k<M;k++){
		for(int i=0;i<M;i++){
			for(int j=0;j<M;j++){
				c[i][j]=max(c[i][j],a[i][k]+b[k][j],cmp);
			}
		}
	}
	return c;
}
#ifdef DEBUG
ostream& operator << (ostream &out,node a){
	return out<<'('<<real(a)<<','<<imag(a)<<')';
}
ostream& operator << (ostream &out,matrix a){
	return out<<"[["<<a[0][0]<<','<<a[0][1]<<"],["<<a[1][0]<<','<<a[1][1]<<"]]";
}
#endif
matrix query(int L,int R,ll k,int l=1,int r=n,int rt=1){
	if(L<=l&&r<=R){
		static matrix res;
		for(int i=0;i<M;i++){
			for(int j=0;j<M;j++){
				auto &f=t[rt][i][j];
				int l=0,r=f.size(),mid;
				for(;l+1<r;){
					mid=(l+r)>>1;
					if(f[mid]>=k)l=mid;
					else r=mid;
				}
				// debug(i,j,k,l);
				res[i][j]=node(s[rt][i][j][l]-l*k,l);
			}
		}
		// debug(l,r,k,res);
		return res;
	}
	int mid=(l+r)>>1;
	if(R<=mid)return query(L,R,k,l,mid,rt<<1);
	if(mid<L)return query(L,R,k,mid+1,r,rt<<1|1);
	return query(L,R,k,l,mid,rt<<1)*query(L,R,k,mid+1,r,rt<<1|1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build();
	for(int x,y,k;m--;){
		scanf("%d%d%d",&x,&y,&k);
		int l=-V,r=V,mid;
		for(;l+1<r;){
			mid=(l+r)>>1;
			auto res=query(x,y,mid)[0];
			if(max(res[0],res[1],cmp).imag()>=k)l=mid;
			else r=mid;
		}
		auto res=query(x,y,l)[0];
		// debug(l,res);
		printf("%lld\n",real(max(res[0],res[1],cmp))+k*l);
	}
	return 0;
}