#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) (x).begin(), (x).end()

#define printf

const int N = 3.5e4 + 10, inf = 1e10;

void chkmax(int &x, int y)
{
	if (y > x) x = y;
}

int cnt;

namespace tree
{
	int n, len[N << 2];
	vector<int> d[N << 2][2][2], sum[N << 2][2][2]; // sum[0] = f(1), f(0) = 0
	int v0[N << 2][2][2];
	
	void pushup(int i)
	{
		for (int c00 : {0, 1}) for (int c11 : {0, 1})
			{
				v0[i][c00][c11] = -inf;
				d[i][c00][c11].resize(len[i], -inf);
				sum[i][c00][c11].resize(len[i], -inf);
				for (int c01 : {0, 1}) for (int c10 : {0, 1})
				{
					vector<int> tmp(d[i << 1][c00][c01].size() + d[i << 1 | 1][c10][c11].size());
					merge(all(d[i << 1][c00][c01]), all(d[i << 1 | 1][c10][c11]), tmp.begin(), greater<int>());
					int tmpv0 = v0[i << 1][c00][c01] + v0[i << 1 | 1][c10][c11];
					chkmax(v0[i][c00][c11], tmpv0);
					int cur = tmpv0;
					for (int x = 0; x < tmp.size(); x++) cur += tmp[x], chkmax(sum[i][c00][c11][x], cur);
					if (c01 && c10)
					{
					 // pop front
						cur = tmpv0 + tmp[0];
						for (int x = 0; x + 1 < tmp.size(); x++) cur += tmp[x + 1], chkmax(sum[i][c00][c11][x], cur);
//					if (i == 4 && c00 == 1 && c11 == 1) 
//					{
//						cout << tmpv0 << '/';
//						for (int x : tmp) cout << x << ' '; cout << endl;
//						assert(tmpv0 <= -2 * inf), assert(sum[i][c00][c11][0] < 0);
//					}
					}
				}
				for (int x = (int)sum[i][c00][c11].size() - 1; x >= 1; x--) d[i][c00][c11][x] = sum[i][c00][c11][x] - sum[i][c00][c11][x - 1];
				d[i][c00][c11].front() = sum[i][c00][c11].front() - v0[i][c00][c11];
				for (int x = 0; x < d[i][c00][c11].size(); x++)
				{
					if (d[i][c00][c11][x] < -5e9)
					{
						for (int j = x; j < d[i][c00][c11].size(); j++) d[i][c00][c11][j] = -inf;
						break;
					}
				}
			}
//		for (int x = 0; x <= len[i]; x++) 
//			for (int c0 : {0, 1}) for (int c1 : {0, 1})
//				f[i][x][c0][c1] = -inf;
//		for (int x = 0; x <= len[i << 1]; x++)
//			for (int y = 0; y <= len[i << 1 | 1]; y++)
//				for (int c00 : {0, 1}) for (int c01 : {0, 1}) for (int c10 : {0, 1}) for (int c11 : {0, 1})
//				{
//					if (f[i << 1][x][c00][c01] <= -inf || f[i << 1 | 1][y][c10][c11] <= -inf) continue;
//					chkmax(f[i][x + y - (c01 && c10)][c00][c11], f[i << 1][x][c00][c01] + f[i << 1 | 1][y][c10][c11]);
//				}
	}
	
	void build(int i, int *a, int li, int ri)
	{
		len[i] = ri - li + 1;
		if (li == ri)
		{
			d[i][0][0].resize(1, -inf), d[i][1][1].resize(1, a[li] + inf), d[i][0][1].resize(1, 0), d[i][1][0].resize(1, 0);
			v0[i][0][0] = 0, v0[i][1][0] = v0[i][0][1] = v0[i][1][1] = -inf;
			for (int c0 : {0, 1})
				for (int c1 : {0, 1}) sum[i][c0][c1] = d[i][c0][c1], sum[i][c0][c1][0] += v0[i][c0][c1];
			return;
		}
		int mid = (li + ri) >> 1;
		build(i << 1, a, li, mid), build(i << 1 | 1, a, mid + 1, ri);
		pushup(i);
	}
	
	void init(int *a, int sz)
	{
		n = sz;
		build(1, a, 1, n);
	}

	void print(int i = 1, int li = 1, int ri = n)
	{
		printf("node %lld : [%lld, %lld]\n", i, li, ri);
		for (int c0 : {0, 1})
			for (int c1 : {0, 1})
			{
				printf("v0(%lld, %lld, %lld) = %lld\n", i, c0, c1, v0[i][c0][c1]);
				printf("sum(%lld, %lld, %lld): ", i, c0, c1);
				for (int x : sum[i][c0][c1]) printf("%lld ", x); printf("\n");
				printf("d(%lld, %lld, %lld): ", i, c0, c1);
				for (int x : d[i][c0][c1]) printf("%lld ", x); printf("\n");
			}
		if (li == ri) return;
		int mid = (li + ri) >> 1;
		print(i << 1, li, mid), print(i << 1 | 1, mid + 1, ri);
	}
	
	typedef array<array<array<int, 2>, 2>, 2> info; // info[c0][c1] = {x, f(x) - px}
	
	info null = {};

	info merge(info x, info y)
	{
		if (x == null) swap(x, y);
		if (y == null) return x;
		
		info res;
		for (int c0 : {0, 1}) for (int c1 : {0, 1}) 
			res[c0][c1] = {0, -inf};
		for (int c00 : {0, 1}) for (int c11 : {0, 1})
		{
			for (int c01 : {0, 1}) for (int c10 : {0, 1})
			{
				int val = x[c00][c01][1] + y[c10][c11][1];
				if (val > res[c00][c11][1]) res[c00][c11] = {x[c00][c01][0] + y[c10][c11][0] - (c01 && c10), val};
			}
		}
		return res;
	}	
	
	info getinfo(int l, int r, int p, int i = 1, int li = 1, int ri = n)
	{
		printf("getinfo(%lld, %lld, %lld, %lld, %lld, %lld)\n", l, r, p, i, li, ri);
		if (l <= li && ri <= r)
		{
			info res;
			for (int c0 : {0, 1}) for (int c1 : {0, 1})
			{
				int id = lower_bound(all(d[i][c0][c1]), p, greater<int>()) - d[i][c0][c1].begin() - 1;
				assert(-1 <= id && id < (int)sum[i][c0][c1].size());
				if (id < 0) res[c0][c1] = {0, v0[i][c0][c1]};
				else res[c0][c1] = {id + 1, sum[i][c0][c1][id]};
				res[c0][c1][1] -= res[c0][c1][0] * p;
			}
			return res;
		}
		int mid = (li + ri) >> 1;
		info cur = null;
		if (l <= mid) cur = getinfo(l, r, p, i << 1, li, mid);
		if (r > mid) cur = merge(cur, getinfo(l, r, p, i << 1 | 1, mid + 1, ri));
		return cur;
	}
}

int n, q, a[N];

//int F(int q, int n)
//{
//	if (q == 0) return 1;
//	if (q == 1) return __lg(n) + 1;
//	if (n == 1) return q;
//	return F(q / 2, n / 2) + F((q + 1) / 2, (n + 1) / 2) + min(q * (__lg(n) + 1) * (__lg(n) + 1), 4 * n);
//}

const int V = 3.5e4 + 10;

signed main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	tree::init(a, n);
	tree::print();
	while (q--)
	{
		int l, r, k; cin >> l >> r >> k;
		int pl = -2 * inf, pr = 2 * inf;
		while (pl < pr)
		{
			int mid = (pl + pr) >> 1;
			auto res = tree::getinfo(l, r, mid);
			int val = -inf, x = 0;
			for (int c0 : {0, 1}) for (int c1 : {0, 1})
				if (res[c0][c1][1] > val) val = res[c0][c1][1], x = res[c0][c1][0];
			printf("x = %lld, val = %lld, pl = %lld, pr = %lld, mid = %lld\n", x, val, pl, pr, mid);
			if (x > k) pl = mid + 1;
			else pr = mid;
		}
		auto res = tree::getinfo(l, r, pl);
		int val = -inf;
		for (int c0 : {0, 1}) for (int c1 : {0, 1})
			chkmax(val, res[c0][c1][1]);
		cout << val + k * pl << endl;
	}
}