WA50，不知道错在哪里了，求助啊qwq

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson root<<1
#define rson root<<1|1
using namespace std;

struct node
{
	int l,r;
	long long sum,lazy;
} tr[2000200];

long long phi[20000010],p[20000010],a[500050],cnt;
bool vis[20000010];

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

inline void get_phi()
{
	phi[1]=1;
	for(register int i=2; i<=20000000; i++)
	{
		if(!vis[i])
		{
			p[++cnt]=i;
			phi[i]=i-1;
		}
		for(register int j=1; j<=cnt; j++)
		{
			if(i*p[j]>20000000)
			{
				break;
			}
			vis[i*p[j]]=1;
			if(i%p[j]==0)
			{
				phi[i*p[j]]=phi[i]*phi[j];
				break;
			}
			else
			{
				phi[i*p[j]]=phi[i]*(p[j]-1);
			}
		}
	}
}

inline void push_up(int root)
{
	tr[root].sum=tr[lson].sum+tr[rson].sum;
}

inline void push_down(int root)
{
	int mid=(tr[root].l+tr[root].r)>>1;
	tr[lson].sum+=tr[root].lazy*(mid-tr[root].l+1);
	tr[lson].lazy+=tr[root].lazy;
	tr[rson].sum+=tr[root].lazy*(tr[root].r-mid);
	tr[rson].lazy+=tr[root].lazy;
	tr[root].lazy=0;
}

inline void build(int root,int l,int r)
{
	if(l==r)
	{
		tr[root].l=l;
		tr[root].r=r;
		tr[root].sum=a[l];
		return ;
	}
	tr[root].l=l;
	tr[root].r=r;
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	push_up(root);
}

inline void update(int root,int l,int r,long long val)
{
	if(tr[root].l==l&&tr[root].r==r)
	{
		tr[root].sum+=val*1ll*(tr[root].r-tr[root].l+1);
		tr[root].lazy+=val;
		return ;
	}
	if(tr[root].lazy)
	{
		push_down(root);
	}
	int mid=(tr[root].l+tr[root].r)>>1;
	if(l>mid)
	{
		update(rson,l,r,val);
	}
	else
	{
		if(mid>=r)
		{
			update(lson,l,r,val);
		}
		else
		{
			update(lson,l,mid,val);
			update(rson,mid+1,r,val);
		}
	}
	push_up(root);
}

inline long long query(int root,int pos)
{
	if(tr[root].l==pos&&tr[root].r==pos)
	{
		return tr[root].sum;
	}
	int mid=(tr[root].l+tr[root].r)>>1;
	if(tr[root].lazy)
	{
		push_down(root);
	}
	if(mid<pos)
	{
		return query(rson,pos);
	}
	else
	{
		return query(lson,pos);
	}
}

inline long long gg(long long a,long long x)
{
	return a<x?a:a%x+x;
}

inline long long kasumi(long long a,long long b,long long c)
{
	long long ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=gg(ans*a,c);
		}
		a=gg(a*a,c);
		b>>=1;
	}
	return ans;
}

inline long long dfs(int l,int r,long long ph)
{
	if(l==r||ph==1)
	{
		a[l]=query(1,l);
		return gg(a[l],ph);
	}
	a[l]=query(1,l);
	return kasumi(a[l],dfs(l+1,r,phi[ph]),ph);
}

int main()
{
//	freopen("testdata.in","r",stdin);
//	freopen("1.out","w",stdout);
	int n,m;
	get_phi();
	n=read();
	m=read();
	for(register int i=1; i<=n; i++)
	{
		a[i]=read();
	}
	build(1,1,n);
	for(; m--;)
	{
		int kd=read(),l=read(),r=read();
		long long val=read();
		if(kd==1)
		{
			update(1,l,r,val);
		}
		if(kd==2)
		{
			printf("%lld\n",dfs(l,r,val)%val);
		}
	}
}