正常点都低于200ms，但是4，5，6，10都T掉了。
感觉好像代码写的有问题，但是查不出错。
是模仿首篇写的。

//g++ i.cpp -o i -std=c++14 -O0 -Wall
#include<iostream>
#include<cstdio>
#define LL long long
#define printf __builtin_printf
using namespace std;
const int maxn=5e5+10,maxc=2e7+10;
int N,M,fc[maxc],fctop=0,phi[maxc];LL f[maxn],a[maxn];
int qd(){
	int rt=0;char c=getchar();
	while(c<'0'||c>'9')  c=getchar();
	while('0'<=c&&c<='9')  rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
	return rt;
}
void pre(){
	phi[1]=1;
	for(int i=2;i<maxc;i++){
		if(!phi[i])  phi[i]=i-1,fc[++fctop]=i;
		for(int j=1;j<=fctop&&1LL*fc[j]*i<maxc;j++){
			if(i%fc[j])  phi[i*fc[j]]=phi[i]*phi[fc[j]];
			else{phi[i*fc[j]]=phi[i]*fc[j];break;}
		}
	}
}
#define lowbit(t) (t&(-t))
void change(int t,int v){for(;t<=N+1;t+=lowbit(t))  f[t]+=v;}
LL ask(int t){a[t]=0;for(int k=t;k;k-=lowbit(k))  a[t]+=f[k];return a[t];}
LL qsm(LL x,int y,int mod){
	LL rt=1;x%=mod;
	for(;y;y>>=1,x=x*x%mod)  if(y&1)  rt=rt*x%mod;
	return rt;
}
LL calc(int l,int r,int mod){
	if(ask(l)%mod==0)  return 0;
	if(l==r)  return a[l]%mod+(a[l]>=mod?mod:0);
	int _r=min(l+5,r);
	for(int i=_r;i>=l;i--)  if(ask(i)==1)  _r=i;
	LL lst=1,p=a[_r];
	for(int i=_r-1;i>l;i--){
		while(p--)  if((lst*=a[i])>mod)  return qsm(a[l],calc(l+1,r,phi[mod])+phi[mod],mod);
		p=lst,lst=1;
	}
	return qsm(a[l],p,mod);
}
int main(){
//	freopen("in.txt","r",stdin);
	N=qd(),M=qd();pre();
//	for(int i=1;i<=20;i++)  printf("%d:phi=%d\n",i,phi[i]);
	for(int i=1,x=0,y;i<=N;i++,x=y)  change(i,(y=qd())-x);
	while(M--){
		int t=qd(),x=qd(),y=qd(),z=qd();
		if(t==1)  change(x,z),change(y+1,-z);
		else printf("%lld\n",calc(x,y,z)%z);
	}
	return 0;
}