我走过你来时的路.

http://acm.hdu.edu.cn/showproblem.php?pid=5634

加深了对于线段树多标记的理解.

//33985526	2020-09-21 20:27:56	Accepted	5634	3010MS	77568K	2730 B	G++	mainland
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e7+10;
// 因为prime的个数很明显达不到maxv的级别
// 这里如果不放心,可以打表来计算一下这里prime开多大比较合适
int prime[maxv/10];
bool np[maxv];
int phi[maxv];
int tot;
// phi 是积性函数,所以可以利用筛来计算
void sieve(int n){
	tot=0; np[1]=true; phi[1]=1;
	inc(i,2,n){
		if(np[i]==false){ prime[++tot]=i; phi[i]=i-1; }
		inc(j,1,tot){
			if(prime[j]*i>n) break;
			np[i*prime[j]]=true;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}



const int N=3e5+10;
#define o rt
#define ls o<<1
#define rs o<<1|1
#define lson l,m,ls
#define rson m+1,r,rs

struct Tree{

    // 表示该节点覆盖的是区间[l,r]
	int l,r;
    // sum表示区间的和
    // same==0 表示该区间内的数并不是相同的,
    // 如果same!=0,表示区间内的数是相同的,且值为same
	ll sum,same;

#define l(x) tree[x].l
#define r(x) tree[x].r

#define sum(x) tree[x].sum
#define same(x) tree[x].same

}tree[N<<2];
inline void pushup(int o){
	sum(o)=sum(ls)+sum(rs);
	if(same(ls)==same(rs)) same(o)=same(ls);
	else same(o)=0;
}

inline void pushdown(int o){
	if(same(o)){
		int l=l(o);
		int r=r(o);
		int m=(l+r)>>1;
		same(ls)=same(rs)=same(o);
		sum(ls)=1LL*same(o)*(m-l+1);
		sum(rs)=1LL*same(o)*(r-m);
		same(o)=0;
	}
}



inline void build(int l,int r,int o){ 
	l(o)=l;
	r(o)=r; 
	if(l==r) { 
		scanf("%lld",&sum(o)); 
		same(o)=sum(o);
		return ; 
	} 
	int m=(l+r)>>1; 
	build(lson);build(rson); 
	pushup(o); 
}
inline void update1(int ql,int qr,int o){ 
	int l=l(o),r=r(o); 

	if(ql<=l && r<=qr && same(o)){
		same(o)=phi[same(o)];
		sum(o)=1LL*same(o)*(r-l+1);
		return ;
	}

	pushdown(o);
	int m=(l+r)>>1;
	if(ql<=m) update1(ql,qr,ls);
	if(m<qr) update1(ql,qr,rs);
	pushup(o);
	return ;
}


inline void update2(int ql,int qr,int x,int o){
	int l=l(o),r=r(o);
	if(ql<=l&& r<=qr){
		same(o)=x;
		sum(o)=1LL*(r-l+1)*x;
		return;
	}
	pushdown(o);
	int m=(l+r)>>1;
	if(ql<=m) update2(ql,qr,x,ls);
	if(m<qr) update2(ql,qr,x,rs);

	pushup(o);

}

ll query(int ql,int qr,int o){
	int l=l(o),r=r(o);
	if(ql<=l && r<=qr) return sum(o);

	pushdown(o);

	int m=(l+r)>>1;
	ll ret=0;
	if(ql<=m) ret+=query(ql,qr,ls);
	if(m<qr) ret+=query(ql,qr,rs);
	return ret;
}


int main(){
	sieve(10000000);
	bool show=true; show=false;

	int T;scanf("%d",&T);while(T--){
		int n,m;scanf("%d%d",&n,&m);
		build(1,n,1);
		inc(i,1,m){
			int op;scanf("%d",&op);
			if(op==1){
				int l,r;scanf("%d%d",&l,&r);
				update1(l,r,1);
			}else if(op==2){
				int l,r,x;scanf("%d%d%d",&l,&r,&x);
				update2(l,r,x,1);
			}else {
				int l,r;scanf("%d%d",&l,&r);
				printf("%lld\n",query(l,r,1));
			}
		}
	}
	return 0;
}