【题意】有一个序列，有3种操作，一种是把区间里面所有的数变成他的欧拉函数值，第二种是把整个区间的数变成某一个值，第三种是查询区间的和。

【解题方法】

这道题其实用线段树来维护就完全可以了，只有当区间的setv存在时，我们更新下去。具体细节见代码。

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=3e5+5;
const int maxm=1e7+5;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//Euler number
int euler[maxm];
void gao(){
     euler[1]=1;
     for(int i=2;i<maxm;i++)
       euler[i]=i;
     for(int i=2;i<maxm;i++)
        if(euler[i]==i)
           for(int j=i;j<maxm;j+=i)
              euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
}
//Segment Tree
struct node{
    int l,r;
    LL setv;
    LL sum;
}Tree[maxn<<2];
void pushup(int rt){
    Tree[rt].sum=Tree[rt*2].sum+Tree[rt*2+1].sum;
    if(Tree[rt*2].setv==Tree[rt*2+1].setv){
        Tree[rt].setv=Tree[rt*2].setv;
    }else{
        Tree[rt].setv=0;
    }
}
void pushdown(int rt){
    int m=(Tree[rt].l+Tree[rt].r)/2;
    if(Tree[rt].setv){
        Tree[rt*2].setv=Tree[rt].setv;
        Tree[rt*2+1].setv=Tree[rt].setv;
        Tree[rt*2].sum=(m-Tree[rt].l+1)*Tree[rt].setv;
        Tree[rt*2+1].sum=(Tree[rt].r-m)*Tree[rt].setv;
        Tree[rt].setv=0;
    }
}
int A[maxn];
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r;
    Tree[rt].setv=0;
    if(l==r){
        Tree[rt].sum=Tree[rt].setv=A[l];
        return ;
    }
    int mid=(l+r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    pushup(rt);
}
void update1(int L,int R,int v,int rt)
{
    if(L==Tree[rt].l&&Tree[rt].r==R){
        Tree[rt].setv=v;
        Tree[rt].sum=(1LL)*v*(Tree[rt].r-Tree[rt].l+1);
        return ;
    }
    pushdown(rt);
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) update1(L,R,v,rt*2);
    else if(L>mid) update1(L,R,v,rt*2+1);
    else{
        update1(L,mid,v,rt*2);
        update1(mid+1,R,v,rt*2+1);
    }
    pushup(rt);
}
void update2(int L,int R,int rt)
{
    if(L==Tree[rt].l&&R==Tree[rt].r&&Tree[rt].setv){
        Tree[rt].setv=euler[Tree[rt].setv];
        Tree[rt].sum=1LL*Tree[rt].setv*(Tree[rt].r-Tree[rt].l+1);
        return ;
    }
    pushdown(rt);
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) update2(L,R,rt*2);
    else if(L>mid) update2(L,R,rt*2+1);
    else{
        update2(L,mid,rt*2);
        update2(mid+1,R,rt*2+1);
    }
    pushup(rt);
}
LL queryans(int L,int R,int rt){
    if(L==Tree[rt].l&&Tree[rt].r==R){
        return Tree[rt].sum;
    }
    pushdown(rt);
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) return queryans(L,R,rt*2);
    else if(L>mid) return queryans(L,R,rt*2+1);
    else{
        return queryans(L,mid,rt*2)+queryans(mid+1,R,rt*2+1);
    }
}
int main()
{
    int T,n,m;
    gao();
    T=read();
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++){
            A[i]=read();
        }
        int op,l,r,x;
        Build(1,n,1);
        for(int i=1; i<=m; i++){
            op=read(),l=read(),r=read();
            if(op==1){
                update2(l,r,1);
            }else if(op==2){
                x=read();
                update1(l,r,x,1);
            }else{
                LL ans=queryans(l,r,1);
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}