讨论区里的 hack 都过了

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 5e5+5,MM = 2e7+5;
LL w[N];
int phi[MM],cnt,p[1333333];
bool vis[MM];

struct tree{int l,r;LL laz;}tr[N<<2];

void build(int l,int r,int i)
{
	tr[i].l = l,tr[i].r = r;
	if(l == r) return (void)(cin >> tr[i].laz);
	int mid = (l+r)>>1;
	build(l,mid,i<<1),build(mid+1,r,i<<1|1);
}

void down(int i)
{
	tr[i<<1].laz += tr[i].laz;
	tr[i<<1|1].laz += tr[i].laz;
	tr[i].laz = 0;
}

void M(int l,int r,int k,int i)
{
	if(tr[i].l >= l &&  tr[i].r <= r)
		return (void)(tr[i].laz += k);
	if(tr[i].laz) down(i);
	if(l <= tr[i<<1].r) M(l,r,k,i<<1);
	if(tr[i<<1|1].l <= r) M(l,r,k,i<<1|1);
}

LL Q(int p,int i)
{
	if(tr[i].l == tr[i].r) return tr[i].laz;
	if(tr[i].laz) down(i);
	if(p <= tr[i<<1].r) return Q(p,i<<1);
	return Q(p,i<<1|1);
}

LL mod(LL x,int p)
{return x >= p ? x%p+p : x;}

LL qp(LL x,int y,int p)
{
	LL res = 1;
	while(y)
	{
		if(y&1) res = mod(res*x,p);
		x = mod(x*x,p),y >>= 1;
	}
	return res;
}

LL D(int l,int r,int p)
{
	if(l == r || p == 1) return mod(Q(l,1),p);
	return qp(Q(l,1)%p,D(l+1,r,phi[p]),p);
}

int main()
{
	phi[1] = 1;
	for (int i = 2;i < MM;i++)
	{
		if(!vis[i]) p[++cnt] = i,phi[i] = i-1;
		for (int j = 1;j <= cnt && p[j]*i < MM;j++)
		{
			vis[p[j]*i] = 1;
			if(!(i%p[j]))
			{
				phi[i*p[j]] = phi[i]*p[j];
				break;
			}
			phi[i*p[j]] = phi[i]*phi[p[j]];
		}
	}
	int n,m;cin >> n >> m;
	build(1,n,1);
	while(m--)
	{
		int op,l,r,x;cin >> op >> l >> r >> x;
		if(op == 1) M(l,r,x,1);
		else cout << D(l,r,x)%x << '\n';
	}
	return 0;
}