#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;
}