#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<vector<tuple<int, int, int>>> queries(n + 1);
    for (int i = 0; i < q; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        l--;
        queries[k].emplace_back(l, r, i);
    }

    vector<ll> ans(q);
    for (int k = 1; k <= n; ++k) {
        if (queries[k].empty()) continue;

        vector<int> mn(n - k + 1);
        deque<int> d;
        for (int i = 0; i < n; ++i) {
            while (!d.empty() && a[d.back()] >= a[i]) {
                d.pop_back();
            }
            d.push_back(i);
            if (i - k + 1 >= 0) {
                mn[i - k + 1] = a[d.front()];
                if (d.front() == i - k + 1) {
                    d.pop_front();
                }
            }
        }
        vector<ll> pref(n - k + 2);
        for (int i = 0; i < mn.size(); ++i) {
            pref[i + 1] = pref[i] + mn[i];
        }
        for (auto [l, r, i] : queries[k]) {
            ans[i] = pref[r - k + 1] - pref[l];
        }
    }

    for (ll x : ans) {
        cout << x << '\n';
    }
}
