#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}
void write(int x){
	if(x/10) write(x/10);
	putchar(x%10+'0');
}
void we(int x){
	write(x);
	putchar('\n');
}
int p,n,m,c,mod[110],gsm1[30][20010],gsm2[30][20010];
inline void mo(int &x){
	if(x>=p) x-=p;
}
inline int phi(int x){
	int ret=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			while(x%i==0) x/=i;
			ret-=ret/i;
		}
	}
	if(x>1) ret-=ret/x;
	return ret;
}
void init(){
	mod[1]=p;
	for(int i=2;mod[i-1]>1;i++) mod[i]=phi(mod[i-1]);
	for(int i=1;mod[i]>1;i++){
		gsm1[i][0]=gsm2[i][0]=1;
		for(int j=1;j<=20000;j++){
			gsm1[i][j]=1ll*gsm1[i][j-1]*c%mod[i];
		}
		for(int j=1;j<=20000;j++){
			gsm2[i][j]=1ll*gsm2[i][j-1]*gsm1[i][20000]%mod[i];
		}
	}
}
int gsm(int idx,int x){
	return 1ll*gsm2[idx][x/20000]*gsm1[idx][x%20000]%mod[idx];
}
int val[200010],ls[50010],a[50010];
bool flag[200010];
inline void push_up(int rt){
	val[rt]=val[rt<<1]+val[rt<<1|1];
	mo(val[rt]);
	flag[rt]=flag[rt<<1]&flag[rt<<1|1];
}
inline int calc(int layer,int now,int ms){
	if(layer==0) return ms;
	if(c==1) return 1;
	if(c%mod[now]==0) return 0;
	if(c%mod[now]==1) return 1;
	if(layer>=6||(layer>=2&&c>=10)) return gsm(now,calc(layer-1,now+1,ms)+mod[now+1]);
	long long las=0,hhh=1;
	for(int i=0;i<ms;i++){
		hhh*=c;
		if(hhh>=mod[now]) return gsm(now,calc(layer-1,now+1,ms)+mod[now+1]);
	}
	if(layer==1) return hhh;
	for(int i=1;i<layer-1;i++){
		las=hhh;
		hhh=1;
		for(int j=0;j<las;j++){
			hhh*=c;
			if(hhh>=mod[now]) return gsm(now,calc(layer-1,now+1,ms)+mod[now+1]);
		}
	}
	return gsm(now,hhh);
}
void build(int rt,int l,int r){
	if(l==r){
		val[rt]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);
}
void update(int rt,int l,int r,int ul,int ur){
	if(flag[rt]) return;
	if(ur<l||ul>r) return;
	if(l==r){
		ls[l]++;
		int tmp=calc(ls[l],1,a[l]);
		if(val[rt]==tmp) flag[rt]=1;
		val[rt]=tmp;
		return;
	}
	int mid=(l+r)>>1;
	update(rt<<1|1,mid+1,r,ul,ur);
	update(rt<<1,l,mid,ul,ur);
	push_up(rt);
}
int query(int rt,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r) return val[rt];
	if(qr<l||ql>r) return 0;
	int mid=(l+r)>>1;
	int ret=query(rt<<1,l,mid,ql,qr)+query(rt<<1|1,mid+1,r,ql,qr);
	mo(ret);
	return ret;
}
int opt,l,r;
int main(){
	n=read();
	m=read();
	p=read();
	c=read();
	init();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	for(int i=1;i<=m;i++){
		opt=read();
		l=read();
		r=read();
		if(opt) we(query(1,1,n,l,r));
		else update(1,1,n,l,r);
	}
	return 0;
}