// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
const int mod=998244353,maxn=50005;
inline void chkmax(int &x,int y){ x=max(x,y); }
inline void chkmin(int &x,int y){ x=min(x,y); }
int a[maxn],n,sjy;
vector<ll>merge(vector<ll>&f,vector<ll>&g){
	if(f.empty()||g.empty()) return {};
	const int fsz=f.size(),gsz=g.size();
	vector<ll>h(fsz+gsz-1);
	int i=1,j=1,k=1; 
	h[0]=f[0]+g[0];
	for(;i<fsz&&j<gsz;++k){
		if(f[i]-f[i-1]>g[j]-g[j-1]) h[k]=h[k-1]+f[i]-f[i-1],++i;
		else h[k]=h[k-1]+g[j]-g[j-1],++j;
	}
	for(;i<fsz;++i,++k) h[k]=h[k-1]+f[i]-f[i-1];
	for(;j<gsz;++j,++k) h[k]=h[k-1]+g[j]-g[j-1];
	return h;
}
#define ls (o<<1)
#define rs (o<<1|1)
vector<ll>t[maxn<<2][2][2],A,B;
void build(int o,int l,int r){
	if(l==r){
		t[o][0][0]={0,a[l]};
		t[o][0][1]=t[o][1][0]=t[o][1][1]={-inf,a[l]};
		return;
	}
	int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r);
	F(i,0,1)F(j,0,1){
		A=merge(t[ls][i][0],t[rs][0][j]);
		B=merge(t[ls][i][1],t[rs][1][j]);
		t[o][i][j].resize(r-l+2);
		F(k,0,r-l) t[o][i][j][k]=max(A[k],B[k+1]);
		t[o][i][j][r-l+1]=A[r-l+1];
	}
}
struct node{
	ll val;int cnt;
	friend node operator+(node x,node y){ return {x.val+y.val,x.cnt+y.cnt}; }
	bool operator<(const node &rhs)const{ return val^rhs.val?val<rhs.val:cnt<rhs.cnt; }
};
#define mat array<array<node,2>,2>
node wqs(vector<ll>&vec,int x){
	int l=1,r=(int)vec.size()-1,pos=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(vec[mid]-vec[mid-1]>=x) pos=mid,l=mid+1;
		else r=mid-1;
	}
	return (node){vec[pos]-pos*x,pos};
}
mat query(int o,int l,int r,int ql,int qr,ll x){
	if(ql<=l&&qr>=r){
		mat tmp;
		F(i,0,1)F(j,0,1)tmp[i][j]=wqs(t[o][i][j],x);
		return tmp;
	}
	int mid=(l+r)>>1;
	if(qr<=mid)return query(ls,l,mid,ql,qr,x);
	if(ql>mid) return query(rs,mid+1,r,ql,qr,x);
	mat L=query(ls,l,mid,ql,qr,x),R=query(rs,mid+1,r,ql,qr,x),res;
	F(i,0,1)F(j,0,1)res[i][j]=max(L[i][0]+R[0][j],L[i][1]+R[1][j]+(node){x,-1});
	return res;
}
void solve(){
	n=read(),sjy=read();
	F(i,1,n)a[i]=read();
	build(1,1,n);
	cmh(sjy){
		int l=read(),r=read(),k=read();
		ll L=-inf,R=inf,pos=R;
		while(L<=R) {
			ll mid=(L+R)>>1;
			if(query(1,1,n,l,r,mid)[0][0].cnt>=k) L=mid+1,pos=mid;
			else R=mid-1;
		}
		ll ans=query(1,1,n,l,r,pos)[0][0].val;
		ans+=1ll*k*pos;
		cout<<ans<<endl;
	}
}
signed main(){
	assert(read()>=0);
	solve();
}