rt,

#include <algorithm>
#include <cmath>
#include <cstdio>

typedef long long ll;

/* ---- read() & rlong() - begin ---- */
#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048576,stdin),p0==p1)?EOF:*p0++)
#define pc(c) (p2==fub+1048576?(fwrite(fub,1048576,1,stdout),*((p2=buf)++)=c):*(p2++)=c)
char buf[1048576],fub[1048576],*p0,*p1,*p2=fub;
inline int read() {
	int r=0; char c=gc(); while (c<48||c>57) c=gc();
	while (c>47&&c<58) {r=(r<<3)+(r<<1)+(c^48); c=gc();} return r;
}
inline ll rlong() {
	ll r=0; char c=gc(); while (c<48||c>57) c=gc();
	while (c>47&&c<58) {r=(r<<3)+(r<<1)+(c^48); c=gc();} return r;
}
inline void write(register ll x){
	static char t[20]; if (!x) {pc(48); pc(10); return;} char *p=t+1;
	t[1]=10; while (x) {*(++p)=(x%10)^48; x/=10;} while (p!=t) pc(*(p--));
}
#undef gc
#undef pc
/* ---- read() & rlong() -- end ----- */

int n,a[100005],s[100005],c[500005],q[500005],f[30000005],g[30000005]; ll b[100005];

inline void insert(register int u,register int v) {
	f[c[u-1]+q[u]]=v; g[c[u-1]+q[u]]=c[u-1]+q[u]; ++q[u];
}

#define lowbit(x) (x&-x)
inline void modify(register int u,register int v) {for (;u<=n;u+=lowbit(u)) b[u]+=v;}

inline ll query (register int u,register int v) {
	register ll w=0; for (--u;u;u^=lowbit(u)) w-=b[u];
	for (;v;v^=lowbit(v)) w+=b[v]; return w;
}
#undef lowbit

inline int find(register int u,register int v) {
	register int w=v; while (w!=g[w]) {if (w>=c[u]) return w; w=g[w];}
	while (v!=w) {g[v]=w; v=g[v];} return w;
}

int main() {
	int m,p,u,v,w; ll l=0; n=read(); m=read();
	for (register int i=1;i<=n;++i) {
		if (!(a[i]=read())) continue;
		s[i]=sqrt(a[i]); modify(i,a[i]); if (a[i]>1) ++c[a[i]];
		for (int j=2;j<s[i];++j) if (!(a[i]%j)) {++c[j]; ++c[a[i]/j];}
		if (!(a[i]%s[i])) {++c[s[i]]; if (s[i]*s[i]<a[i]) ++c[a[i]/s[i]];}
	}
	for (register int i=2;i<500001;++i) c[i]+=c[i-1];
	for (register int i=1;i<=n;++i) {
		if (!a[i]) continue; if (a[i]>1) insert(a[i],i);
		for (int j=2;j<s[i];++j) if (!(a[i]%j)) {insert(j,i); insert(a[i]/j,i);}
		if (!(a[i]%s[i])) {insert(s[i],i); if (s[i]*s[i]<a[i]) insert(a[i]/s[i],i);}
	}
	while (m--) switch (read()) {
		case 1:
			u=rlong()^l; v=rlong()^l; w=rlong()^l; if (w==1) break;
			p=std::lower_bound(f+c[w-1],f+c[w],u)-f;
			for (register int i=find(w,p);i<c[w]&&f[i]<=v;i=find(w,i+1)) {
				if (!(a[f[i]]%w)) {modify(f[i],a[f[i]]/w-a[f[i]]); a[f[i]]/=w;}
				if (a[f[i]]%w) g[i]=i+1;
			}
			break;
		case 2: u=rlong()^l; v=rlong()^l; write(l=query(u,v)); break;
	}
	fwrite(fub,p2-fub,1,stdout);
	return 0;
}

还有之前用vector<>写的版本