#include <bits/stdc++.h>
//#include <bits/extc++.h>
using namespace std;
#define int long long
//__gnu_pbds::gp_hash_table<int,int> ma;
map<pair<int,int> ,int> ma;
int phi(int id){
	int ans=id,vis=0;
	for(int j=2;j*j<=id;j++){
		if(id%j==0){
			ans=ans/j;
			ans*=(j-1);
			vis=1;
			while(id%j==0){
				id/=j;
			}
		}
	}
	if(id>1){
		return ans/id*(id-1);
	}
	return ans;
}
int Ph[1919810],now;
int n,m,p,c;
int kuai_mi(int y,int Mod){
//	if(ma[make_pair(y,Mod)]){
//		return ma[make_pair(y,Mod)];
//	}
	int x=c;
	int ans=1,vis=0;
	while(y){
		if(y&1){
			ans*=x;
		}
		x*=x;
		if(ans>=Mod){
			ans%=Mod;
			vis=1;
		}
		if(x>=Mod && y>1){
			ans%=Mod;
			vis=1;
		}
		x%=Mod;
		y>>=1;
	}
	if(vis){
		ans+=Mod;
	}
	ma[make_pair(y,Mod)]=ans;
	return ans;
}
int P[100005][65];
int a[1919810],sum[1919810];
int tree[1919810],vis[1919810];
void build(int id,int l,int r){
	if(l==r){
		tree[id]=a[l];
		return;
	} 
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tree[id]=tree[id*2]+tree[id*2+1];
}
int dfs(int id){
	if(id==1){
		return 1;
	}
	return 1+dfs(phi(id));
}
int ans=0;
int ddfs(int id,int Mod,int ida,int num){
	if(ida==num){
		return kuai_mi(id,Mod);
	}
	int anaa=ddfs(id,Ph[ida],ida+1,num);
	int ans=kuai_mi(anaa,Mod);
	return ans;
}
void change(int id,int l,int r,int L,int R){
	if(L<=l && r<=R && vis[id]){
		return;
	}
	if(l==r){
		sum[l]--;
		tree[id]=ddfs(a[l],p,1,ans-sum[l])%p;
		if(sum[l]==0){
			vis[id]=1;
			return;
		}
		return;
	}
	int mid=(l+r)/2;
	if(R<=mid){
		change(id*2,l,mid,L,R);
	}else if(L>mid){
		change(id*2+1,mid+1,r,L,R);
	}else{
		change(id*2,l,mid,L,R);
		change(id*2+1,mid+1,r,L,R);
	}
	tree[id]=tree[id*2]+tree[id*2+1];
	vis[id]=(vis[id*2]&vis[id*2+1]);
}
int query(int id,int l,int r,int L,int R){
	if(L<=l && r<=R){
		return tree[id];
	}
	int mid=(l+r)/2;
	if(R<=mid){
		return query(id*2,l,mid,L,R);
	}else if(L>mid){
		return query(id*2+1,mid+1,r,L,R);
	} else{
		return (query(id*2,l,mid,L,R)+query(id*2+1,mid+1,r,L,R))%p;
	}
}
signed main(){
	cin>>n>>m>>p>>c;
	int nnn=p;
	while(p){
		if(p==1){
			break;
		}
		p=phi(p);
		Ph[++now]=p;
	}
		Ph[++now]=p;
	p=nnn;
	ans=now;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=ans;
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==0){
			int l,r;
			cin>>l>>r;
//			for(int j=l;j<=r;j++){
//				sum[j]=max(sum[j]-1,0)
//			}
			change(1,1,n,l,r);
		}else{
			int l,r;
			cin>>l>>r;
			cout<<query(1,1,n,l,r)%p<<'\n';
		}
	}
	
	return 0;
}
//1845808
//1845808

是对的而把

int kuai_mi(int y,int Mod){
//	if(ma[make_pair(y,Mod)]){
//		return ma[make_pair(y,Mod)];
//	}
	int x=c;
	int ans=1,vis=0;
	while(y){
		if(y&1){
			ans*=x;
		}
		x*=x;
		if(ans>=Mod){
			ans%=Mod;
			vis=1;
		}
		if(x>=Mod && y>1){
			ans%=Mod;
			vis=1;
		}
		x%=Mod;
		y>>=1;
	}
	if(vis){
		ans+=Mod;
	}
	ma[make_pair(y,Mod)]=ans;
	return ans;
}

改成

int kuai_mi(int y,int Mod){
	if(ma[make_pair(y,Mod)]){
		return ma[make_pair(y,Mod)];
	}
	int x=c;
	int ans=1,vis=0;
	while(y){
		if(y&1){
			ans*=x;
		}
		x*=x;
		if(ans>=Mod){
			ans%=Mod;
			vis=1;
		}
		if(x>=Mod && y>1){
			ans%=Mod;
			vis=1;
		}
		x%=Mod;
		y>>=1;
	}
	if(vis){
		ans+=Mod;
	}
	ma[make_pair(y,Mod)]=ans;
	return ans;
}

就错了，求解释，如果你帮我找到了问题，我就让同学给你关注