RT，96pts，超时两个点都是500+ms，感觉我要行了

#include <cstdio>
#include <vector>
#include <algorithm>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 65536, stdin), p1 == p2) ? EOF : *p1 ++)

char buf[65536], *p1, *p2;
inline int read()  {
	char ch;
	int x(0);
	while ((ch = gc) < 48);
	do x = x * 10 + ch - 48; while ((ch = gc) >= 48);
	return x;
}

const int N = 500005;
inline int max(const int x, const int y) {return x > y ? x : y;}

int a[N], mem[45000005], tot, n;
struct Vector {
	int stpos, endpos;
	inline void push_back(const int x) {
		stpos ? mem[endpos = ++ tot] = x : mem[stpos = endpos = ++ tot] = x;
	}
	inline int& operator [] (const int x) const {return mem[stpos + x];}
	inline int* begin() {return mem + stpos;}
	inline int *end() {return mem + endpos + 1;}
	inline int size() {return stpos ? endpos - stpos + 1 : 0;}
	inline bool empty() {return !stpos;}
};
long long c[N];
std::vector<int> cnt[N];
inline void update(const long long x, const long long d) {
	for (int i(x); i <= n; i += (i & ~i + 1)) c[i] += d;
}
inline long long query(const int x) {
	long long sum(0LL);
	for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
	return sum;
}

struct Reap {
	Vector fac, fa;
	int find(const int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
	inline void upd(const int l, const int r, const int x) {
		if (fac.empty()) return;
		int i(find(std::lower_bound(fac.begin(), fac.end(), l) - fac.begin()));
		while (i < fac.size() && fac[i] <= r) {
			a[fac[i]] % x ? fa[i] = find(i + 1) : update(fac[i], a[fac[i]] / x - a[fac[i]]), a[fac[i]] /= x;
			i = find(i + 1);
		}
	}
} s[N];

int main() {
	int m, t(0);
	long long last(0LL);
	n = read(), m = read();
	for (int i(1); i <= n; ++ i)
		t = max(t, a[i] = read()), update(i, a[i]), cnt[a[i]].push_back(i);
	for (int i(2); i <= t; ++ i)
		for (int j(i); j <= t; j += i)
			for (auto k : cnt[j]) s[i].fac.push_back(k);
	for (int i(1); i <= t; ++ i) {
		if (s[i].fac.size()) std::sort(s[i].fac.begin(), s[i].fac.end());
		for (int j(0); j <= s[i].fac.size(); ++ j) s[i].fa.push_back(j);
	}
	while (m --) {
		int op(read()), l(read() ^ last), r(read() ^ last), x;
		if (op == 1) {
			x = read() ^ last;
			if (x != 1) s[x].upd(l, r, x);
		}
		else printf("%lld\n", last = query(r) - query(l - 1));
	}
}