#\
p\
r\
a\
g\
m\
a\
 \
G\
C\
C\
 \
t\
a\
r\
g\
e\
t\
(\
"\
a\
v\
x\
,\
s\
s\
e\
2\
,\
s\
s\
e\
3\
,\
s\
s\
e\
4\
,\
m\
m\
x\
"\
)
#include<bits/stdc++.h>
using namespace std; 
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,2097152,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline int read(){
    int w(0);
	char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')w=w*10+(c^48),c=getchar();
    return w;
}
inline void print(long long x) {
    if(x>9) print(x/10);
    *O++=x%10+'0';
}
inline long long readll(){
    long long w(0);
	char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')w=w*10+(c^48),c=getchar();
    return w;
}
long long tree[100003];//树状数组
int n,m;
inline long long query(int x)
{
    long long res=0;
    while(x) res+=tree[x],x-=x&(-x);
    return res;
}
inline void add(int x,int k)
{
    while(x<=n) tree[x]+=k,x+=x&(-x);
    return ;
}
int a[100003];
int v[2][22000003];//内存池
int s[500003],pos[500003];
inline int Find(int y)
{
    if(v[1][y]==y) return y;
    return v[1][y]=Find(v[1][y]);
}
inline int BS(int l,int r,int tgt)
{
    int res=r;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(v[0][mid]>=tgt) res=mid,r=mid-1; else l=mid+1;
    }
    return res;
}
signed main()
{
    //double S=clock();
    n=read(),m=read();
    for(int i=1; i<=n; i++) a[i]=read(),add(i,a[i]),++s[a[i]];
    for(int i=2; i<=250000; ++i) { for(int j=2; i*j<=500000; ++j) s[i]+=s[i*j]; s[i]+=s[i-1]+1; }
    for(int i=250001; i<=500001; ++i) s[i]+=s[i-1]+1;
    for(int i=1; i<=s[500001]; ++i) v[1][i]=i;
    for(int i=500001; i>=2; --i) s[i]=s[i-1],pos[i]=s[i]-1;
    for(int i=1,j; i<=n; ++i)
    {        
        if(a[i]<=1) continue;
        v[0][++pos[a[i]]]=i;
        for(j=2; j*j<a[i]; ++j) if(!(a[i]%j)) 
        v[0][++pos[j]]=i,v[0][++pos[a[i]/j]]=i;
        if(j*j==a[i]) v[0][++pos[j]]=i;
    }
    for(int i=2; i<=500000; ++i) v[0][++pos[i]]=1919810,sort(v[0]+s[i],v[0]+s[i+1]);
    for(long long lst=0;m--;)
    {
        int opt=read(),l=(readll()^lst),r=(readll()^lst);
        if(l>r) swap(l,r);
        if(opt&1)
        {
            int x=(readll()^lst),cnt=0;
            if(x==1) continue;
            int st=Find(BS(s[x],s[x+1]-1,l));
            for(int i=st; v[0][i]<=r; i=Find(i+1))
            {
                int tmp=v[0][i];
                if(a[tmp]%x) 
                { 
                    v[1][i]=Find(i+1);
                    continue; 
                }
                add(tmp,-a[tmp]),a[tmp]/=x,add(tmp,a[tmp]);
                if(a[tmp]%x) v[1][i]=Find(i+1);
            }
        }
        else print(lst=(query(r)-query(l-1))),*O++='\n';
    }
    fwrite(obuf,O-obuf,1,stdout);
    //double T=clock();
    //cout<<(T-S)/CLOCKS_PER_SEC<<endl;
	return 0;
}

卡了一天了……谁来救救我