rt，弱化版过了，然而不会卡常，code：

#include <bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
ll Read() {
	int sig = 1;
	ll num = 0;
	char c = getchar();
	while(!isdigit(c)) {
		if(c == '-') {
			sig = -1;
		}
		c = getchar();
	}
	while(isdigit(c)) {
		num = (num << 3) + (num << 1) + (c ^ 48);
		c = getchar();
	}
	return num * sig;
}
void Write(ll x) {
	if(x < 0) {
		putchar('-');
		x = -x;
	}
	if(x >= 10) {
		Write(x / 10);
	}
	putchar((x % 10) ^ 48);
}

const int N = 100005, M = 500005, K = 22000005;
int n, m, a[N];
struct tNode {
	int val, nxt;
}e[M];
int head[M], p[K], len[M], cnt;
inline void Add(int u, int v) {
	e[++cnt] = {v, head[u]};
	head[u] = cnt;
}
const int inf = 1e9;
struct DSU {
	int fa[K];
	inline void Init(int n) {
		int i;
		for(i = 1; i <= n; i++) {
			fa[i] = i;
		}
	}
	inline int Find_Root(int x) {
		return (fa[x] == x) ? x : (fa[x] = Find_Root(fa[x]));
	}
	inline void Join(int x, int y) {
		int rx = Find_Root(x), ry = Find_Root(y);
		if(x > y) {
			swap(rx, ry);
		}
		fa[rx] = ry;
	}
}dsu;
inline int BS(int x, int ql) {
	int l = 1, r = len[x] - len[x - 1], mid, res = len[x] - len[x - 1] + 1;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(p[len[x - 1] + mid] < ql) {
			l = mid + 1;
		}
		else {
			res = mid;
			r = mid - 1;
		}
	}
	return res + len[x - 1];
}
inline int BS2(int x, int qr) {
	int l = 1, r = len[x] - len[x - 1], mid, res = 0;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(p[len[x - 1] + mid] <= qr) {
			res = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	return res + len[x - 1];
}
struct Tree_Array {
	int n;
	ll tree[N];
	inline void Add(int x, ll add) {
		while(x <= n) {
			tree[x] += add;
			x += x & -x;
		}
	}
	inline ll Query(int x) {
		ll res = 0;
		while(x) {
			res += tree[x];
			x -= x & -x;
		}
		return res;
	}
}ta;
int main() {
	re int i, j, k;
	int maxa = -1e9;
	n = Read(), m = Read();
	ta.n = n;
	for(i = 1; i <= n; i++) {
		a[i] = Read();
		maxa = max(maxa, a[i]);
		Add(a[i], i);
		ta.Add(i, a[i]);
	}
	int c = 0;
	for(i = 1; i <= M - 5; i++) {
		for(j = i; j <= M - 5; j += i) {
			for(k = head[j]; k; k = e[k].nxt) {
				p[++c] = e[k].val;
				len[i]++;
			}
		}
		len[i] += len[i - 1];
		stable_sort(p + len[i - 1] + 1, p + len[i] + 1);
	}
	dsu.Init(c + 114514);
	ll lastans = 0;
	while(m--) {
		ll op = Read(), l = Read() ^ lastans, r = Read() ^ lastans;
		if(op == 1) {
			ll x = Read() ^ lastans;
			if(x == 1 || x > maxa) {
				continue;
			}
			int ml = BS(x, l), mr = BS2(x, r);
			if(ml > mr) {
				continue;
			}
			i = dsu.Find_Root(ml);
//			set<int> s;
			while(i >= ml && i <= mr) {
//				if(s.count(i)) {
//					exit(114);
//				}
//				s.insert(i);
				if(a[p[i]] % x == 0) {
					a[p[i]] /= x;
					ll d = 1ll * a[p[i]] * (x - 1);
					ta.Add(p[i], -d);
				}
				if(a[p[i]] % x > 0) {
					if(i < len[x]) {
						dsu.Join(i, i + 1);
						i++;
					}
					else {
						dsu.Join(i, c + 1);
						i = c + 1;
					}
				}
				else {
					i++;
				}
				i = dsu.Find_Root(i);
			}
		}
		else {
			Write(lastans = ta.Query(r) - ta.Query(l - 1)), putchar('\n');
		}
	}
	return 0;
}