#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <fstream>
#include <string>
#include <set>
#include <deque>
#include <queue>
#include <map>
#include <bitset>
#include <random>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <cstdlib>
using namespace std;
#define all(a)            a.begin(), a.end()
#define lf '\n'
typedef int ll;
typedef long long ll2;
typedef pair<ll, ll> pll;
const ll inf = 1e9;
vector<vector<ll>> vals;
unordered_map<ll, vector<ll2>> prefs;
size_t n, m;
vector <ll> a;

void build(size_t v, size_t tl, size_t tr) {
    if (tl == tr) {
        vals[v] = vector<ll>(1, a[tl]);
    }
    else {
        size_t tm = (tl + tr) >> 1;
        size_t left = (v << 1);
        size_t right = left | 1;
        build(left, tl, tm);
        build(right, tm + 1, tr);
        merge(vals[left].begin(), vals[left].end(), vals[right].begin(), vals[right].end(), back_inserter(vals[v]));
        ll sum = 0;/*
        for (size_t i = 0; i < vals[v].size(); ++i) {
            sum += vals[v][i];
            prefs[v][i] = sum;
        }*/
    }
}
unordered_map <ll, ll2> save;
ll2 sum_seg(vector<ll>& v, vector<ll2>& p, ll cur, ll mod) {
    ll2 res = 0;
    if (v.size() == 0)
        return res;

    if (save.find(cur) != save.end())
        return save[cur];

    auto beg = v.begin();
    ll2 mx = *(v.rbegin());
    ll kmax = mx / mod;

    while (beg != v.end()) {
        ll2 mn = *beg;
        ll2 cnt = distance(beg, v.end());
        ll2 idx = distance(v.begin(), beg);
        if (mn == mx) {
            res += (ll2)(mn % mod) * cnt;
            break;
        }
        ll kmin = mn / mod;
        if (kmin == kmax) {
            res += (ll2)(*(p.rbegin()) - (idx == 0 ? 0 : p[idx - 1])) - (ll2)mod * kmin * cnt;
            break;
        }
        auto nxt = lower_bound(beg, v.end(), (kmin + 1) * mod);
        auto prv = prev(nxt);
        size_t idx2 = distance(v.begin(), prv);
        ll2 cnt2 = distance(beg, nxt);
        res += (ll2)(p[idx2] - (idx == 0 ? 0 : p[idx - 1])) - (ll2)mod * kmin * cnt2;

        beg = nxt;
    }
    save[cur] = res;
    return res;
}

ll2 sum(size_t v, size_t tl, size_t tr, size_t l, size_t r, ll mod) {
    if (l > r)
        return 0;

    if (l == tl && r == tr) {

        if (prefs[v].empty()) {
            prefs[v].resize(vals[v].size());
            ll2 sum = 0;
            for (size_t i = 0; i < vals[v].size(); ++i) {
                sum += vals[v][i];
                prefs[v][i] = sum;
            }
        }
        return sum_seg(vals[v], prefs[v], v, mod);
    }
    size_t tm = (tl + tr) >> 1;
    return sum(v << 1, tl, tm, l, min(r, tm), mod) + sum((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r, mod);
}
const ll c = 3000;
ll pref[c + 1];
signed main() {
    ll t = 1;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //cin >> t;
    while (t--) {
        cin >> n >> m;
        ll sub = 1;
        while (sub < n)sub *= 2;
        a.resize(sub * 2);
        vals.resize(sub * 2);
        ll i;
        for (i = 0; i < n; ++i) {
            cin >> a[i];
        }

        vector<ll2> ans(m);
        struct event {
            ll x, type;
            ll mod;
            ll ind;
        };
        struct bigger {
            ll l, r;
            ll mod;
            ll ind;
        };
        vector<event> line;
        vector<bigger> big_sqrt;
        for (i = 0; i < m; ++i) {
            ll l, r, mod;
            cin >> l >> r >> mod;
            --l, --r;
            if (mod <= c) {
                line.push_back({ l, 1, mod, i });
                line.push_back({ r, -1, mod, i });
            }
            else {
                big_sqrt.push_back({ l,r,mod,i });
            }
        }
        auto cmp = [&](event& lht, event& rht) {
            if (lht.x == rht.x) {
                return lht.type > rht.type;
            }
            return lht.x < rht.x;
        };
        sort(all(line), cmp);
        ll ind = 0;
        for (int i = 0; i <= c; i++)
            pref[i] = 0;
        for (event& i : line) {
            while (ind < i.x) {
                for (ll j = 1; j <= c; j++) {
                    pref[j] += (a[ind]) % j;
                }
                ind++;
            }
            if (i.type == 1) {
                ans[i.ind] = -pref[i.mod];
            }
            else {
                ans[i.ind] += (ll2)pref[i.mod] + (ll2)a[ind] % i.mod;
            }
        }
        build(1, 0, n - 1);
        //ll sss = 0;
        ll last = -inf;
        for (bigger& i : big_sqrt) {
            if (last != i.mod && last != -inf) {
                save.clear();
            }
            last = i.mod;
            ll ql = i.l, qr = i.r, modd = i.mod, to = i.ind;
            ans[to] = sum(1, 0, n - 1, ql, qr, modd);
        }
        for (ll2& now : ans) {
            cout << now << endl;
        }
        //cout << sss << endl;
    }
    return 0;
}