开O2和不开O2相差无几（

最大的点600多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], n;
long long c[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 {
	std::vector<int> 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) {
			if (a[fac[i]] % x) fa[i] = find(i + 1);
			else 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]);
	for (int i(1); i <= n; ++ i) {
		for (int j(2); j * j <= a[i]; ++ j)
			if (a[i] % j == 0) {
				s[j].fac.push_back(i);
				if (j * j != a[i]) s[a[i] / j].fac.push_back(i);
			}
		s[a[i]].fac.push_back(i);
	}
	for (int i(1); i <= t; ++ i)
		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));
	}
}