T先不说，为什么会WA？

#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
int n,m,phi[20000005]= {0,1},opt,x,y,z,mod[100005],cnt,a;
long long tree[500005];
struct check {
	ll val;
	bool flag;
};
inline void add(int sum,int k) {
	if(!k)return;
	while(k<=n) {
		tree[k]+=sum;
		k+=lowbit(k);
	}
}
inline int query(int k) {
	int res=0;
	while(k) {
		res+=tree[k];
		k-=lowbit(k);
	}
	return res;
}
inline check qpow(ll d,int p,int md) {
	check res;
	res.val=1,res.flag=0;
	if(d>=md)d%=md,res.val=1;
	while(p) {
		if(p&1) {
			res.val*=d;
			if(res.val>=md)res.flag=1,res.val%=md;
		}
		d*=d;
		if(d>=md)res.flag=1,d%=md;
		p>>=1;
	}
	return res;
}
inline check ask(int l,int r,int md) {
	check res;
	int t=query(l);
	if(md==1)return (check) {
		0,1
	};
	else if(t==1)return (check) {
		1,0
	};
	else if(l==r&&t>=md)return (check) {
		t%md,1
	};
	else if(l==r&&t<md)return (check) {
		t,0
	};
	else {
		res=ask(l+1,r,phi[md]);
		if(res.flag)res.val+=phi[md];
		return qpow(t,res.val,md);
	}
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a);
		add(a,i);
		add(-a,i+1);
	}
	for(int i=2; i<=2e7; i++) {
		if(!phi[i]) {
			for(int j=i; j<=2e7; j+=i) {
				if(!phi[j])phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
		}
	}
	while(m--) {
		scanf("%d%d%d%d",&opt,&x,&y,&z);
		if(opt==1)
			add(-z,y+1),add(z,x);
		else printf("%d\n",ask(x,y,z).val%z);
	}
}