#include <bits/stdc++.h>
#define reint register int
//#define int long long
using namespace std;
const int N=5e4+10;
struct node{
	int l,r,s,tim;
} t[N*4]; 
int n,m,p,c,pricnt,phicnt,a[N],pri[N],phi[N],pw1[40][N],pw2[40][N];
bool vis[N],b1[40][N],b2[40][N];
int Phi(int x){
	int res=x;
	for(reint i=2;i<=pricnt && pri[i]*pri[i]<=x;i++){
		if(x%pri[i]==0){
			while(x%pri[i]==0){
				x/=pri[i];
			}
			res=res/pri[i]*(pri[i]-1);
		}
	}
	if(x>1){
		res=res/x*(x-1);
	}
	return res;
}
void get(){
	for(reint i=2;i<=10000;i++){
		if(!vis[i]){
			pri[++pricnt]=i;
		}
		for(reint j=1;j<=pricnt && i*pri[j]<=10000;j++){
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){
				break;
			}
		}
	}
	phi[phicnt]=p;
	while(phi[phicnt]!=1){
		phicnt++;
		phi[phicnt]=Phi(phi[phicnt-1]);
	}
	phi[++phicnt]=1; 
}
void init(){
	get();
	for(reint i=0;i<=phicnt;i++){
		pw1[i][0]=1;
		for(reint j=1;j<=10000;j++){
			pw1[i][j]=(1ll*pw1[i][j-1]*c)%phi[i];
			b1[i][j]=(b1[i][j-1]|(1ll*pw1[i][j-1]*c>=phi[i]));
		}
	}
	for(reint i=0;i<=phicnt;i++){
		pw2[i][0]=1;
		for(reint j=1;j<=10000;j++){
			pw2[i][j]=(1ll*pw2[i][j-1]*pw1[i][10000])%phi[i];
			b2[i][j]=(b2[i][j-1]|(1ll*pw2[i][j-1]*pw1[i][10000]>=phi[i]));
		}
	}
}
void pushup(int rt){
	t[rt].s=(t[rt*2].s+t[rt*2+1].s)%p;
	t[rt].tim=min(t[rt*2].tim,t[rt*2+1].tim);
}
void build(int rt,int l,int r){
	t[rt].l=l;
	t[rt].r=r;
	if(l==r){
		t[rt].s=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	pushup(rt);
}
pair<int,int> phipow(int b,int id){
	int v1=b%10000,v2=b/10000,res=1ll*pw1[id][v1]*pw2[id][v2]%phi[id];
	return make_pair(res,((1ll*pw1[id][v1]*pw2[id][v2]>=phi[id])|(b1[id][v1]|b2[id][v2])));
}
int calc(int a,int x){
	int t=a;
	if(t>phi[x]){
		t=t%phi[x]+phi[x];
	}
	for(reint i=x;i;i--){
		pair<int,int> pr=phipow(t,i-1);
		t=pr.first;
		if(pr.second){
			t+=phi[i-1];
		}
	}
	return t;
}
void modify(int rt,int l,int r){
	if(t[rt].l>r || t[rt].r<l){
		return ;
	}
	if(t[rt].tim>=phicnt){
		return ;
	}
	if(t[rt].l==t[rt].r){
		t[rt].tim++;
		t[rt].s=calc(a[t[rt].l],t[rt].tim);
		return ;
	}
	modify(rt*2,l,r);
	modify(rt*2+1,l,r);
	pushup(rt);
}
int query(int rt,int l,int r){
	if(t[rt].l>r || t[rt].r<l){
		return 0;
	}
	if(t[rt].l>=l && t[rt].r<=r){
		return t[rt].s;
	}
	return (query(rt*2,l,r)+query(rt*2+1,l,r))%p;
}
signed main(){
	cin >>n>>m>>p>>c;
	for(reint i=1;i<=n;i++){
		cin >>a[i];
	}
	init();
	build(1,1,n);
	while(m--){
		int op,l,r;
		cin >>op>>l>>r;
		if(op==0){
			modify(1,l,r);
		}else{
			cout <<query(1,l,r)<<"\n";
		}
	}
	return 0;
}