#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128

#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
template <class T ENABLE_IF_INT>
constexpr T INF = numeric_limits<T>::max() >> 1;
#endif

#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define For(i, j, k) for (decltype(j - k) i = (j); i <= (k); ++i)     // NOLINT
#define ForDown(i, j, k) for (decltype(j - k) i = (j); i >= (k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
template<typename T> constexpr il T sq(const T & x){ return x * x; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y);}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y, T mod){T ans = 1; x %= mod; while (y) { if(y & 1)(ans *= x) %= mod;(x *= x) %= mod; y >>= 1;} return ans;}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y){T ans = 1; while (y) {if(y & 1) ans *= x;x *= x;y >>= 1;} return ans;}
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while(!isdigit(c)) {if (c == '-') f = -1;c = getchar();} while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();} x *= f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x); read(y...); }
// clang-format on

// File head end

namespace {
constexpr ll MAXN = 35005, INF = 1e14;
int n, q, a[MAXN];
struct Node {
  int l, r;
  array<vector<ll>, 4> val;
  array<int, 4> id;
} T[MAXN << 2];
#define mid(p) ((T[p].l + T[p].r) >> 1)
#define sz(p) (T[p].r - T[p].l + 1)
#define lc(p) (mid(p) << 1)
#define rc(p) (mid(p) << 1 | 1)
il vector<ll> merge(const vector<ll> &x, const vector<ll> &y) {
  if (x.empty() || y.empty())
    return {};
  vector<ll> res = {x[0] + y[0]};
  for (ll p = 1, q = 1, cur = res[0]; p < x.size() || q < y.size();) {
    if (q == y.size() || (p < x.size() && x[p] - x[p - 1] >= y[q] - y[q - 1]))
      res.eb(cur += x[p] - x[p - 1]), p++;
    else
      res.eb(cur += y[q] - y[q - 1]), q++;
  }
  return res;
}
il void pu(int p) {
  T[p].val[0] = T[p].val[1] = T[p].val[2] = T[p].val[3] = {};
  For(i, 0, 3) For(j, 0, 3) {
    int k = (i >> 1) << 1 | (j & 1);
    auto vec = merge(T[lc(p)].val[i], T[rc(p)].val[j]);
    if (T[p].val[k].size() < vec.size())
      T[p].val[k].resize(vec.size(), -INF);
    For(o, 0, signed(vec.size()) - 1) cmax(T[p].val[k][o], vec[o]);
    if (i & (j >> 1) & 1)
      For(o, 1, signed(vec.size()) - 1) cmax(T[p].val[k][o - 1], vec[o]);
  }
}
void build(int p, int l, int r) {
  T[p].l = l, T[p].r = r, T[p].id = {0, 0, 0, 0};
  if (l == r) {
    T[p].val[3] = {-INF, a[l]};
    T[p].val[0] = {0};
    T[p].val[1] = T[p].val[2] = {};
    return;
  }
  int mid = (l + r) >> 1;
  build(lc(p), l, mid), build(rc(p), mid + 1, r);
  pu(p);
}
void reset(int p) {
  T[p].id = {0, 0, 0, 0};
  if (T[p].l == T[p].r)
    return;
  reset(lc(p)), reset(rc(p));
}
array<ll, 4> qry(int p, int ql, int qr, ll V) {
  if (ql <= T[p].l && qr >= T[p].r) {
    auto search = [&](int i) {
      int &id = T[p].id[i];
      const auto &val = T[p].val[i];
      while (id + 1 < val.size() &&
             val[id + 1] - V * (id + 1) > val[id] - V * id)
        id++;
      return val[id] - V * id;
    };
    array<ll, 4> res = {search(0), search(1), search(2), search(3)};
    return res;
  }
  int mid = mid(p);
  if (qr <= mid)
    return qry(lc(p), ql, qr, V);
  else if (ql > mid)
    return qry(rc(p), ql, qr, V);
  else {
    array<ll, 4> ans = {-INF, -INF, -INF, -INF}, L = qry(lc(p), ql, qr, V),
                 R = qry(rc(p), ql, qr, V);
    For(i, 0, 3) For(j, 0, 3) {
      int k = (i >> 1) << 1 | (j & 1);
      cmax(ans[k], L[i] + R[j]);
      if (i & (j >> 1) & 1)
        cmax(ans[k], L[i] + R[j] + V);
    }
    return ans;
  }
}
using qry_t = tuple<ll, ll, int>;
qry_t Qry[MAXN], res[MAXN];
ll Ans[MAXN], tmp[MAXN];

// il ll solve(int L, int R, int K) {
//   ll l = -3e9, r = 3e9;
//   auto q2 = qry(1, L, R, r + 1);
//   ll ans = *max_element(q2.begin(), q2.end()) + 1ll * K * (r + 1);
//   while (l <= r) {
//     ll mid = (l + r) / 2;
//     auto q1 = qry(1, L, R, mid), q2 = qry(1, L, R, mid + 1);
//     ll v1 = *max_element(q1.begin(), q1.end()) + 1ll * K * mid,
//        v2 = *max_element(q2.begin(), q2.end()) + 1ll * K * (mid + 1);
//     if (v1 > v2)
//       l = mid + 1;
//     else
//       ans = v1, r = mid - 1;
//   }
//   return ans;
// }

il void Main() {
  read(n, q);
  For(i, 1, n) read(a[i]);
  build(1, 1, n);
  For(i, 1, q) {
    read(get<0>(Qry[i]), get<1>(Qry[i]), get<2>(Qry[i]));
    res[i] = {-3e9, 3e9, i};
  }
  For(_, 1, 33) {
    sort(res + 1, res + 1 + q, [&](const auto &x, const auto &y) {
      return (get<0>(x) + get<1>(x)) / 2 > (get<0>(y) + get<1>(y)) / 2;
    });
    reset(1);
    For(i, 1, q) if (get<0>(res[i]) <= get<1>(res[i])) {
      ll L, R, K, mid = (get<0>(res[i]) + get<1>(res[i])) >> 1;
      tie(L, R, K) = Qry[get<2>(res[i])];
      auto q1 = qry(1, L, R, mid);
      tmp[i] = *max_element(q1.begin(), q1.end()) + 1ll * K * mid;
    }
    reset(1);
    For(i, 1, q) if (get<0>(res[i]) <= get<1>(res[i])) {
      ll L, R, K, mid = (get<0>(res[i]) + get<1>(res[i])) >> 1;
      tie(L, R, K) = Qry[get<2>(res[i])];
      auto q2 = qry(1, L, R, mid + 1);
      ll v2 = *max_element(q2.begin(), q2.end()) + 1ll * K * (mid + 1);
      if (tmp[i] > v2)
        get<0>(res[i]) = mid + 1;
      else
        Ans[get<2>(res[i])] = tmp[i], get<1>(res[i]) = mid - 1;
    }
  }
  For(i, 1, q) cout << Ans[i] << '\n';
}
} // namespace

signed main() { return Main(), 0; }