#include <bits/stdc++.h>
#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
#define down(i,a,b) for (int i = (int)a; i >= (int)b; i--)
#define int long long
#define all(x) x.begin(), x.end()
using namespace std;

const int maxn = 2e5 + 10;
const int LOG = log2(maxn) + 1;
int a[maxn];
int logg[maxn];
int sp[LOG][maxn];
int n,q;

void build_gcd(int n){
    sp[0][1] = a[1];
    up(i,2,n){
        logg[i] = logg[(i >> 1)] + 1;
        sp[0][i] = a[i];
    }
    for (int i = 1; (1 << i) <= n; i++){
        for (int j = 1; j + (1 << i) - 1 <= n; j++){
            sp[i][j] = __gcd(sp[i-1][j], sp[i-1][j + (1 << (i-1))]);
        }
    }
}

int get(int l, int r){
    int k = logg[r - l + 1];
    return __gcd(sp[k][l], sp[k][r - (1 << k) + 1]);
}

struct Query{
    int d, l, r, type;
    bool operator < (const Query& O){
        if (d == O.d) return type < O.type;
        return d < O.d;
    }
};

vector<Query> Q;
int F[maxn];
/**
Gọi F[i] là vị trí xa nhất về phía bên phải của i
F[i] >= i;
sao cho gcd(i, F[i]) <= d
**/

int BIT[maxn];
void update(int x, int val){
    while (x <= n){
        BIT[x] += val;
        x += (x & (-x));
    }
}
int get(int x){
    int res = 0;
    while (x){
        res += BIT[x];
        x -= (x & (-x));
    }
    return res;
}

void make_prefix_sum(){
    up(i,1,n){
        BIT[i] = BIT[i-1] + n+1;
        F[i] = n+1;
    }
    down(i,n,1){
        BIT[i] -= BIT[i - (i & (-i))];
    }
}

void init_offline(){
    up(i,1,n){
        int pos = i;
        up(loop, 0, 29){
            int L = pos;
            int R = n+1;
            int cur_GCD = get(i, pos);
            while (R - L > 1){
                int MID = (L+R) >> 1;
                if (get(i, MID) == cur_GCD) L = MID;
                else R = MID;
            }
            Q.push_back({cur_GCD, i, pos, -1});
            pos = L+1;
            if (pos > n) break;
        }
    }
}

int res[maxn];
void solve(){
    for (auto& que : Q){
        int l = que.l;
        int r = que.r;
        int type = que.type;
        if (type < 0){
            update(l, -F[l]);
            F[l] = r;
            update(l, F[l]);
        }
        else{
            int L = l;
            int R = r+1;
            while (R - L > 1){
                int MID = (L+R) >> 1;
                if (F[MID] <= r) L = MID;
                else R = MID;
            }
            if (F[L] > r) res[type] = 0;
            else res[type] = (r + 1)*(L - l + 1) - (get(L) - get(l-1));
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #define Task "A"
    if (fopen(Task".inp", "r")){
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }

    cin >> n >> q;
    up(i,1,n) cin >> a[i];
    build_gcd(n);

    init_offline();
    up(i,1,q){
        int l,r,d;
        cin >> l >> r >> d;
        Q.push_back({d, l, r, i});
    }
    sort(all(Q));

    make_prefix_sum();

    solve();
    up(i,1,q) cout << res[i] << "\n";
}