标题是真的/tuu

#include<bits/stdc++.h>
#define i64 long long
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#ifdef ONLINE_JUDGE
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
#endif
template<typename T>
inline void read(T &x)
{
	x=0;i64 f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	x*=f;
}
template<typename T,typename ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
const int N=1e5+5,V=5e5+5,Z=3e7;
struct
{
	int *fa;
	void init(int sz){for(int i=0;i<sz;i++)fa[i]=i;}
	int find(int u){return (fa[u]==u)?u:(fa[u]=find(fa[u]));}
}t[V];
int n,m,v,a[N],ct[V],*p[V],pl[Z],*tp=pl;
i64 c[N],l,r,x,lst;
void update(int u,int w){for(int i=u;i<=n;i+=i&-i)c[i]+=w;}
i64 query(int u){int r=0;for(int i=u;i;i-=i&-i)r+=c[i];return r;}
void modify(int l,int r,int x)
{
	if(x==1)return;
	l=lower_bound(p[x],p[x]+ct[x],l)-p[x];
	r=upper_bound(p[x],p[x]+ct[x],r)-p[x]-1;
	if(l>r)return;
	for(int i=t[x].find(l),w;i<=r;)
	{
		w=p[x][i];
		if(a[w]%x==0)
		{
			update(w,a[w]/x-a[w]);
			a[w]/=x;
		}
		if(i>=r)break;
		if(a[w]%x)i=t[x].fa[i]=t[x].find(i+1);
		else i=t[x].find(i+1);
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("university.in","r",stdin);
	freopen("university.out","w",stdout);
	#endif
	read(n,m);
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		update(i,a[i]);
		ct[a[i]]=1;
		v=max(v,a[i]);
	}
	for(int i=1;i<=v;i++)for(int j=(i<<1);j<=v;j+=i)ct[i]+=ct[j];
	for(int i=1;i<=v+1;i++)if(ct[i])
	{
		p[i]=tp;tp+=ct[i];t[i].fa=tp;
		t[i].init(ct[i]);tp+=ct[i];ct[i]=0;
	}
	for(int i=1;i<=n;i++)for(int j=1;j*j<=a[i];j++)if(a[i]%j==0)
	{
		p[j][ct[j]++]=i;
		if(j*j!=a[i])p[a[i]/j][ct[a[i]/j]++]=i;
	}
	for(int i=1,op;i<=m;i++)
	{
		read(op,l,r);
		l^=lst;r^=lst;
		if(op==1)
		{
			read(x);x^=lst;
			modify(l,r,x);
		}
		else
		{
			lst=query(r)-query(l-1);
			printf("%lld\n",lst);
		}
	}
}