第二个样例过不了

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<stdio.h>
#include<map>
#include<set>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include<bitset>
using namespace std;
const int N=5e4+5;
int n,m,mod,c;

bool vis[10005];
int prime[10005],phi[10005],tot,ci;
int Phi(int x){
	int re=x;
	for(int i=1;i<=tot;i++){
		if(x%prime[i]==0){
			re=re/prime[i]*(prime[i]-1);
			while(x%prime[i]==0){
				x/=prime[i];
			}
		}
	}
	if(x!=1)re=re/x*(x-1);
	return re;
} 
void init(){
	for(int i=2;i<=10000;i++){
		if(!vis[i]){
			phi[i]=i-1;
			prime[++tot]=i;
			int j=i*2;
			while(j<=10000){
				vis[j]=1;
				j+=i;
			}
		}
	} 
	phi[0]=mod;
	while(phi[ci]!=1){
		ci++;
		phi[ci]=Phi(phi[ci-1]);
	}
	ci--;
	//phi[++ci]=1;
}
long long pow1[55][10005],pow2[55][10005];
bool dal[55][10004],dar[55][10008];
void work(){
	for(int i=0;i<=ci;i++){
		pow2[i][0]=1;
		for(int j=1;j<=10000;j++){
			pow2[i][j]=(pow2[i][j-1]*c)%phi[i];
			dar[i][j]=dar[i][j-1]|(pow2[i][j-1]*c>=phi[i]);
		}
	}
	for(int i=0;i<=ci;i++){
		pow1[i][0]=1;
		//dal[i][0]=dar[i][10000];
		for(int j=1;j<=10000;j++){
			pow1[i][j]=(pow1[i][j-1]*pow2[i][10000])%phi[i];
			dal[i][j]=dal[i][j-1]|(pow1[i][j-1]*pow2[i][10000]>=phi[i]);
		}
		//dal[i][0]=0;
	}
}
int a[N];
long long tree[N*4];long long minn[N*4];
void pushup(int x){
	tree[x]=(tree[x*2]+tree[x*2+1])%mod;
	minn[x]=min(minn[x*2],minn[x*2+1]);
}
void build(int x,int l,int r){
	if(l==r){
		tree[x]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid);build(x*2+1,mid+1,r);
	pushup(x);
}
int f;
long long pow(int x,int y){
	long long re=pow1[x][y/10000]*pow2[x][y%10000];
	if(re>phi[x])f=1;
	f|=dal[x][y/10000]|dar[x][y%10000];
	return re;
}
long long dfs(int x,int y){
	for(int i=y;i>=1;i--){
		f=0;
		x=pow(i-1,x);
		if(f==1)x+=phi[i-1];
	}
	return x;
}
void update(int x,int l,int r,int ql,int qr){
	if(minn[x]>=ci)return;
	if(l==r){
		++minn[x];
		tree[x]=dfs(a[l],minn[x]);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid){
		update(x*2,l,mid,ql,qr);
	}
	if(qr>mid){
		update(x*2+1,mid+1,r,ql,qr);
	}
	pushup(x);
}
long long query(int x,int l,int r,int ql,int qr){
	long long re=0;
	if(ql<=l&&r<=qr){
		return tree[x];
	}
	int mid=(l+r)/2;
	if(ql<=mid)re=query(x*2,l,mid,ql,qr);
	if(qr>mid)re+=query(x*2+1,mid+1,r,ql,qr);
	return re%mod;
}
int main(){
	cin>>n>>m>>mod>>c;
	for(int i=1;i<=n;i++)cin>>a[i];
	init();work(); 
	build(1,1,n);
	while(m--){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==0){
			update(1,1,n,l,r);
		}else{
			cout<<query(1,1,n,l,r)<<endl;
		}
	}
	return 0;
}