// https://szkopul.edu.pl/problemset/problem/q6f5K7O79TpYR7yuZVrQpy_d/site/?key=statement

#include <bits/stdc++.h>

// using namespace std;

// #define GARY_DBG
#define GARY_LIB

#define int long long

constexpr int sizik = 1000 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

struct Wavelet {
    int lo, hi;
    std::vector<int> b; // b[i] = # elements among first i that go to left child
    std::vector<int> pref; // pref sum of first i elements (their original values)
    std::vector<int> leftPref; // pref sum of elements that went left among first i
    Wavelet *L = nullptr, *R = nullptr;
    const std::vector<int>* valsPtr; // pointer to sorted-unique values by rank

    // data: std::vector of ranks (0..m-1) for this node's subsequence
    Wavelet(const std::vector<int>& data, const std::vector<int>& vals, int loIdx, int hiIdx) : lo(loIdx), hi(hiIdx) {
        valsPtr = &vals;
        int n = data.size();
        b.assign(n + 1, 0);
        pref.assign(n + 1, 0);
        leftPref.assign(n + 1, 0);
        if (n == 0) return;
        if (lo == hi) {
            // leaf: all elements have same value = vals[lo]
            for (int i = 0; i < n; ++i) {
                pref[i + 1] = pref[i] + (*valsPtr)[data[i]];
                leftPref[i + 1] = leftPref[i] + (*valsPtr)[data[i]];
                b[i + 1] = b[i] + 1; // everything goes to "left" in leaf representation (not used deeply)
            }
            return;
        }
        int mid = (lo + hi) >> 1;
        std::vector<int> leftData;
        leftData.reserve(n);
        std::vector<int> rightData;
        rightData.reserve(n);
        for (int i = 0; i < n; ++i) {
            int rank = data[i];
            pref[i + 1] = pref[i] + (*valsPtr)[rank];
            if (rank <= mid) {
                b[i + 1] = b[i] + 1;
                leftPref[i + 1] = leftPref[i] + (*valsPtr)[rank];
                leftData.push_back(rank);
            } else {
                b[i + 1] = b[i];
                leftPref[i + 1] = leftPref[i];
                rightData.push_back(rank);
            }
        }
        if (!leftData.empty()) L = new Wavelet(leftData, vals, lo, mid);
        if (!rightData.empty()) R = new Wavelet(rightData, vals, mid + 1, hi);
    }

    // query: sum of k largest numbers in interval [l,r] (1-indexed indices into this node's sequence)
    int sum_k_largest(int l, int r, int k) {
        if (l > r || k <= 0) return 0LL;
        int len = r - l + 1;
        if (k >= len) {
            // take all elements sum
            return pref[r] - pref[l - 1];
        }
        if (lo == hi) {
            // all values equal to vals[lo]
            return (int)k * (*valsPtr)[lo];
        }
        // number of elements that went to right child in [l,r]
        int leftCount = b[r] - b[l - 1];
        int rightCount = len - leftCount;

        if (rightCount >= k) {
            // we can take all k from right subtree
            int newL = l - b[l - 1];
            int newR = r - b[r];
            return R->sum_k_largest(newL, newR, k);
        } else {
            // take everything from right subtree, plus (k - rightCount) from left subtree
            int totalRangeSum = pref[r] - pref[l - 1];
            int leftRangeSum = leftPref[r] - leftPref[l - 1];
            int rightRangeSum = totalRangeSum - leftRangeSum;
            // mapping to left child indices:
            int newL = b[l - 1] + 1;
            int newR = b[r];
            return rightRangeSum + L->sum_k_largest(newL, newR, k - rightCount);
        }
    }
};

int d[sizik], pref[sizik];

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> vals;
    for (int i = 1; i <= n; i++) {
        std::cin >> d[i];
        if (i & 1)
            vals.push_back(d[i]);
        else
            vals.push_back(0);

        pref[i] = pref[i - 1] + d[i];
    }

    assert(pref[0] == 0);

    std::sort(vals.begin(), vals.end());
    vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
    int m = (int)vals.size();
    std::vector<int> ranks(n);
    std::unordered_map<int, int> mp;
    mp.reserve(2 * m);
    for (int i = 0; i < m; i++) {
        mp[vals[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        int x = d[i + 1];
        if (i & 1) x = 0;
        ranks[i] = mp[x];
    }

    // magic !
    Wavelet wt(ranks, vals, 0, m - 1);

    for (; q > 0; q--) {
        int l, r, k;
        std::cin >> l >> r >> k;

        auto l_ptr = std::lower_bound(pref, pref + n + 1, l);
        l_ptr++;

        auto r_ptr = std::lower_bound(pref, pref + n + 1, r);
        r_ptr--;

        int l_idx = std::distance(pref, l_ptr);
        int r_idx = std::distance(pref, r_ptr);

        if (l_ptr > r_ptr) {
            int x = std::distance(pref, l_ptr - 1);
            int y = std::distance(pref, r_ptr + 1);
            if ((x & 1) != (y & 1)) {
                if (k < 1) {
                    std::cout << "0\n";
                } else if (x & 1) {
                    l_ptr--;
                    int z = *l_ptr - l + 1;
                    std::cout << z << '\n';
                } else {
                    int z = r - (*r_ptr + 1) + 1;
                    std::cout << z << '\n';
                }
            } else if (x & 1) {
                std::cout << r - l + 1 << '\n';
            } else {
                std::cout << 0 << '\n';
            }

            continue;
        }

        if (k == 0) {
            std::cout << "0\n";
            continue;
        }

        int l1 = l_idx;
        int r1 = r_idx;

        int x1 = (pref[l_idx - 1] - l + 1);
        int x2 = (r - pref[r_idx]);

        if ((std::distance(pref, l_ptr) & 1)) {
            x1 = 0;
        }

        if ((std::distance(pref, r_ptr) & 1)) {
            x2 = 0;
        }

        int ans = 0;
        int seglen = r1 - l1 + 1;

        auto gg_k = [&](int k1) -> int {
            if (k1 > seglen) return seglen;
            return k1;
        };

        int k_prime = gg_k(k / 2);
        int wyn = wt.sum_k_largest(l1, r1, k_prime);
        ans = std::max(ans, wyn);

        if (k >= 1) {
            k_prime = gg_k((k - 1) / 2);
            wyn = wt.sum_k_largest(l1, r1, k_prime);
            wyn += std::max(x1, x2);
            ans = std::max(ans, wyn);
        }

        if (k >= 2) {
            k_prime = gg_k((k - 2) / 2);
            wyn = wt.sum_k_largest(l1, r1, k_prime);
            wyn += x1 + x2;
            ans = std::max(ans, wyn);
        }

        std::cout << ans << '\n';
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}