#include <iostream>
#include <vector>

using namespace std;

const int N = 1000010;

using i64 = long long;

struct Node{
    int l, r;
    int val;
    int sz;
} tr[N * 40];
int nodes[N * 40], tt;
int n, m, k;
int root[N], idx;
int a[N], q[N];
vector<int> pos[N];

int new_node(int val) {
    int u = tt ? nodes[tt--] : ++idx;
    tr[u].l = tr[u].r = 0;
    tr[u].val = val;
    tr[u].sz = 1;
    return u;
}

void pushup(int u) {
    tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1;
}

int build(int l, int r) {
    if (l > r) return 0;
    int mid = l + r >> 1;   
    int u = new_node(q[mid]);
    tr[u].l = build(l, mid - 1);
    tr[u].r = build(mid + 1, r);
    pushup(u);
    return u;
}

void split(int u, int val, int &x, int &y) {
    if (!u) return x = y = 0, void();
    if (tr[u].val <= val) {
        x = u;
        split(tr[u].r, val, tr[u].r, y);
        pushup(x);
    } else {
        y = u;
        split(tr[u].l, val, x, tr[u].l);
        pushup(y);
    }
}

int merge(int x, int y) {
    if (!x or !y)  return x | y;    
    if (rand() % (tr[x].sz + tr[y].sz) < tr[x].sz) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
    return 0;
}

struct Fenwick {
    i64 tr[N];
    inline int lowbit(int x) {
        return x & -x;
    }
    inline void add(int x, int v) {
        for (; x <= n; x += lowbit(x))
            tr[x] += v;
    }
    inline i64 ask(int x) {
        i64 res = 0;
        for (; x; x -= lowbit(x))
            res += tr[x];
        return res;
    }
    inline i64 ask(int l, int r) {
        return ask(r) - ask(l - 1);
    }
} t;

void divide(int pos, int x) {
    t.add(pos, a[pos] / x - a[pos]);
    a[pos] /= x;
}

void dfs(int u, int x) {
    if (!u) return;
    dfs(tr[u].l, x);
    if (a[tr[u].val] % x == 0) divide(tr[u].val, x);
    if (a[tr[u].val] % x == 0) q[++k] = tr[u].val;
    dfs(tr[u].r, x);
    nodes[++tt] = u;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 1; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                if (j != 1) pos[j].emplace_back(i);
                if (j != a[i] / j) pos[a[i] / j].emplace_back(i);
            }
        }
        t.add(i, a[i]);
    }
    for (int i = 2; i <= 1000000; i++) {
        k = 0;
        for (auto p : pos[i]) q[++k] = p;
        root[i] = build(1, k);
    }
    while (m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            int p1, p2, p3;   
            split(root[x], l - 1, p1, p2); 
            split(p2, r, p2, p3);
            k = 0;  
            dfs(p2, x);
            p2 = build(1, k); 
            root[x] = merge(merge(p1, p2), p3); 
        }
        if (op == 2) {
            cout << t.ask(l, r) << '\n';
        }
    }
    return 0;
}