#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;

const int INF = 0x3f3f3f3f;

typedef pair <long long, int> pli;

pli operator + (const pli &A, const pli &B) {
	return mp(A.fi + B.fi, A.se + B.se);
}

int a[100010];
int POOL[20000000], *CUR = POOL;

void SeqMul(int *f, int n, int *g, int m, int *h) {
	static int tmp[100010];
	int p = 0, q = 0, cur = 0;
	while (p < n || q < m) {
		tmp[cur++] = q == m || p < n && f[p] > g[q] ? f[p++] : g[q++];
	}
	for (int i = 0; i < cur; i++) {
		h[i] = tmp[i];
	}
}

void SeqMax(int *f, int n, int *g, int *h) {
	static int tmp[100010];
	int sf = 0, sg = 0;
	for (int i = 0; i < n; i++) {
		if (f[i] == -INF) sf = -INF;
		else sf += f[i];
		if (g[i] == -INF) sg = -INF;
		else sg += g[i];
		tmp[i] = max(sf, sg);
	}
	for (int i = 0; i < n; i++) {
		h[i] = tmp[i] == -INF ? -INF : tmp[i] - (i ? tmp[i - 1] : 0);
	}
}

pli GetVal(int *f, int n, int *sum, int delta) {
	int pos = upper_bound(f, f + n, delta, greater <int>()) - f;
	return mp((pos ? sum[pos - 1] : 0) - 1ll * pos * delta, pos);
}

namespace SEG {
	struct Node {
		int *f[2][2], *sum[2][2], n;
		void GetMem(int sz) {
			n = sz;
			for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
				f[i][j] = CUR, CUR += sz;
				sum[i][j] = CUR, CUR += sz;
			}
		}
		void GetSum() {
			for (int p = 0; p < 2; p++) for (int q = 0; q < 2; q++) {
				for (int i = 0; i < n; i++) {
					if (f[p][q][i] == -INF) break;
					sum[p][q][i] = f[p][q][i] + (i ? sum[p][q][i - 1] : 0);
				}
			}
		}
		void GetTrans(int delta, pli trans[2][2]) {
			for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
				trans[i][j] = GetVal(f[i][j], n, sum[i][j], delta);
			}
		}
	}T[1 << 18];
	vector <Node> ans;
	void Build(int now, int l, int r) {
		T[now].GetMem(r - l + 1);
		if (l == r) {
			for (int p = 0; p < 2; p++) for (int q = 0; q < 2; q++) {
				T[now].f[p][q][0] = p && q ? a[l] : -INF;
			}
			T[now].GetSum();
			return ;
		}
		int mid = l + r >> 1;
		Build(now << 1, l, mid), Build(now << 1 | 1, mid + 1, r);
		for (int p = 0; p < 2; p++) for (int q = 0; q < 2; q++) {
			static int tmp[100010];
			SeqMul(T[now << 1].f[p][1], mid - l + 1, T[now << 1 | 1].f[0][q], r - mid, T[now].f[p][q]);
			SeqMul(T[now << 1].f[p][0], mid - l + 1, T[now << 1 | 1].f[1][q], r - mid, tmp);
			SeqMax(tmp, r - l + 1, T[now].f[p][q], T[now].f[p][q]);
		}
		T[now].GetSum();
	}
	void Query(int now, int l, int r, int L, int R) {
		if (now == 1) ans.clear();
		if (l == L && r == R) {
			ans.push_back(T[now]);
			return ;
		}
		int mid = l + r >> 1;
		if (R <= mid) Query(now << 1, l, mid, L, R);
		else if (L > mid) Query(now << 1 | 1, mid + 1, r, L, R);
		else Query(now << 1, l, mid, L, mid), Query(now << 1 | 1, mid + 1, r, mid + 1, R);
	}
	pli Calc(int delta) {
		static pli dp[2]; dp[0] = mp(0, 0), dp[1] = mp(0, 0);
		for (auto it : ans) {
			static pli trans[2][2]; it.GetTrans(delta, trans);
			static pli tmp[2];
			tmp[0] = max(dp[0] + trans[1][0], dp[1] + trans[0][0]);
			tmp[1] = max(dp[0] + trans[1][1], dp[1] + trans[0][1]);
			dp[0] = tmp[0], dp[1] = tmp[1];
		}
		return dp[1];
	}
}

int main() {
	int n, q; scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	SEG :: Build(1, 1, n);
	while (q--) {
		int l, r, k; scanf("%d%d%d", &l, &r, &k);
		SEG :: Query(1, 1, n, l, r);
		{
			int l = -k * 10010, r = 10001;
			while (l < r) {
				int mid = (l + 1000000000ll + r + 1000000000ll + 1 >> 1) - 1000000000ll;
				if (SEG :: Calc(mid).se < k) r = mid - 1;
				else l = mid;
			}
			auto it = SEG :: Calc(l);
			printf("%lld\n", it.fi + 1ll * k * l);
		}
	}
	return 0;
}