#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
typedef unsigned int ui;
typedef long long             ll;
typedef unsigned long long     ull;
typedef long double            ld;
#define endl              "\n"
#define all(a)            a.begin(), a.end()
#define allr(a)           a.rbegin(), a.rend()
#define pb                push_back
#define pikachu           push_back
#define F                 first
#define S                 second
struct node {
    ll mx, sum;
};
struct segtree {
    node main_val, used_val;
};
const ll MAXN = 2e5 + 1;
segtree tree[4 * MAXN]; ll a[MAXN];
void build(ll v, ll tl, ll tr) {
    if (tl == tr) {
        tree[v].main_val = { a[tl],a[tl] };
        tree[v].used_val = { a[tl],a[tl] };
        return;
    }
    ll mid = (tr + tl) / 2;
    build(v * 2, tl, mid);
    build(v * 2 + 1, mid + 1, tr);
    tree[v].main_val = { max(tree[v * 2].main_val.mx,tree[v * 2 + 1].main_val.mx),tree[v * 2].main_val.sum + tree[v * 2 + 1].main_val.sum };
    tree[v].used_val = { max(tree[v * 2].used_val.mx,tree[v * 2 + 1].used_val.mx),tree[v * 2].used_val.sum + tree[v * 2 + 1].used_val.sum };
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll mod) {
    if (tl > r || tr < l) {
        return;
    }
    if (tree[v].main_val.mx < mod) {
        tree[v].used_val.mx = tree[v].main_val.mx;
        tree[v].used_val.sum = tree[v].main_val.sum;
        return;
    }
    if (tl == tr) {
        tree[v].used_val.mx = tree[v].main_val.mx % mod;
        tree[v].used_val.sum = tree[v].used_val.mx;
        return;
    }
    ll mid = (tr + tl) / 2;
    update(v * 2, tl, mid, l, r, mod);
    update(v * 2 + 1, mid + 1, tr, l, r, mod);
    tree[v].used_val = { max(tree[v * 2].used_val.mx,tree[v * 2 + 1].used_val.mx),tree[v * 2].used_val.sum + tree[v * 2 + 1].used_val.sum };
}
ll get_sum(ll v, ll tl, ll tr, ll l, ll r, ll mod) {
    if (tl > r || tr < l) {
        return 0;
    }
    if (tl >= l && tr <= r) {
        if (tree[v].main_val.mx < mod) {
            return tree[v].main_val.sum;
        }
        return tree[v].used_val.sum;
    }
    ll mid = (tr + tl) / 2;
    return get_sum(v * 2, tl, mid, l, r, mod) +
        get_sum(v * 2 + 1, mid + 1, tr, l, r, mod);
}
struct question {
    ll l, r, x;
    ll ind;
};
struct Line {
    ll l, r;
};
unordered_map <ll, vector<question>> compres;
vector<Line> Scanline(vector<question>& sub) {
    struct event {
        ll x, type;
    };
    vector<event> scan;
    for (question& i : sub) {
        scan.push_back({ i.l,+1 });
        scan.push_back({ i.r,-1 });
    }
    sort(all(scan), [](event lht, event rht) {
        return (lht.x < rht.x || (lht.x == rht.x && lht.type > rht.type));
        });
    vector<Line> coordinates_to_update;
    ll l = -1, r = -1;
    ll balance = 0;
    for (event& i : scan) {
        if (!balance) {
            l = i.x;
        }
        else if (balance + i.type == 0) {
            r = i.x;
            coordinates_to_update.push_back({ l,r });
        }
        balance += i.type;
    }
    return coordinates_to_update;
}
void solve() {
    ll n, m;
    cin >> n >> m;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    build(1, 0, n - 1);
    vector<ll> ans(m);
    vector<question>q(m);
    for (ll i = 0; i < m; i++) {
        ll l, r, x;
        cin >> l >> r >> x;
        q[i] = { --l,--r, x ,i };
    }
    auto cmp = [&](question lht, question rht) {
        return lht.x < rht.x;
    };
    sort(all(q), cmp);
    for (question& i : q) {
        compres[i.x].push_back(i);
    }
    ll cnt = 0;
    // lst last = { -1,-1,-1 };
    for (auto& i : compres) {
        vector<Line> upd = Scanline(i.second);
        for (auto&& [l, r] : upd) {
            update(1, 0, n - 1, l, r, i.first);
        }
        for (question j : i.second) {
            ans[j.ind] = get_sum(1, 0, n - 1, j.l, j.r, i.first);
        }
    }
    for (ll i = 0; i < m; i++) {
        cout << ans[i] << endl;
    }
}
signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}