#include <bits/stdc++.h>
using namespace std;

int n,m;
long long a[100010];
int ss[100001];
long long  last;

int *fa[500001];
int *fa2[500001];
int cnt[45555555];
int *poi=cnt;
long long  o[500001];
int maxx;


inline void add(int x,long long k)
{
    while(x<=n)
    {
        a[x]+=k;
        x+=(x&(-x));
    }
}

long long sum(int x)
{
    long long he=0;
    while(x>0)
    {
        he+=a[x];
        x=x-(x&-x);
    }
    return he;
}


int read( )
{
    int f=0;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        f=f*10+ch-'0';
        ch=getchar();
    }
    return f;
}

int find(int x,int k)
{
    if(k==o[x]||k==fa2[x][k])return k;
    return fa2[x][k]=find(x,fa2[x][k]);
}

inline void write(long long  X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
signed main( )
{
    n=read( );
    m=read( );
    for(int i=1;i<=n;++i)
    {
        ss[i]=read();
        maxx=max(ss[i],maxx);
        add(i,ss[i]);
        o[ss[i]]++;
    }
    for(int i=1;i<=maxx;i++)
    for(int j=i+i;j<=maxx;j=j+i)
    o[i]=o[i]+o[j];
    
    for(int i=1;i<=maxx;i++)
    {
        fa2[i]=poi;
        poi=poi+o[i];
        fa[i]=poi;
        poi=poi+o[i];
        for(int j=0;j<o[i];j++)fa2[i][j]=j;
        o[i]=0;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j*j<=ss[i];j++)
    {
        if(ss[i]%j==0)
        {
            fa[j][o[j]++]=i;
            if(ss[i]!=j*j)
            {
                fa[ss[i]/j][o[ss[i]/j]++]=i;
            }
        }
    }
    
    int kind,l,r,x;
    for(int i=1;i<=m;++i)
    {
        kind=read( );
        if(kind==1)
        {
            l=read( ),r=read( ),x=read( ),l^=last,r^=last,x^=last;
            if(x==1)continue;
            if(o[x]==0)continue;
            int wei=lower_bound(fa[x],fa[x]+o[x],l)-fa[x];
            for(int j=find(x,wei);j<o[x]&&fa[x][j]<=r;j=find(x,j+1))
            {
                if(ss[fa[x][j]]%x==0)
                {
                    int o=fa[x][j];
                    ss[o]=ss[o]/x;
                    add(o,(long long)(-ss[o]*(x-1)));
                    
                }
                if(ss[fa[x][j]]%x!=0)fa2[x][j]=j+1;
            }
        }
        else{
            l=read( ),r=read( ),l^=last,r^=last;
            last=sum(r)-sum(l-1);
            write(last);
            putchar('\n');
        }
    }
    return 0;
}

差了48ms