#include<bits/stdc++.h>
#define L 40
#define int long long
#define ls id<<1,l,(l+r)>>1
#define rs id<<1|1,((l+r)>>1)+1,r
using namespace std;
inline int phi(int x)
{
	int res=x;
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
		{
			res-=res/i;
			while(x%i==0) x/=i;
		}
	if(x>1) res-=res/x;
	return res;
}
int n,m,p,c,pp[L+5],pw[L+5][2][65536],a[50005][L+5],num[50005];
inline int P(int x,int y)
{return pw[y][0][x&65535]*pw[y][1][x>>16]%pp[y];}
inline bool check(int x,int y,int z)
{
	if(x==0) return y<=z;
	if(c==1) return z>=1;
	long double res=y;
	for(int i=1;i<=x;i++)
	{
		if(res-0.5>z) return 0;
		if(res>32) return 0;
		res=pow(x,res);
	}
	if(res-0.5>z) return 0;
	return 1;
}
inline int solve(int x,int y,int z)//(x ge c)^y%pp[z]
{
	if(x==0) return y%pp[z];
	int res;
	if(check(x-1,y,pp[z+1])) res=P(solve(x-1,y,z+1),z);
	else res=P(solve(x-1,y,z+1)+pp[z+1],z);
//	cout<<x<<' '<<y<<' '<<z<<' '<<check(x-1,y,pp[z+1])<<' '<<res<<endl;
	return res;
}
struct bcj{
	int fa[50005];
	inline void init(int x)
	{
		for(int i=1;i<=x;i++) fa[i]=i;
	}
	inline int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
	inline void merge(int x,int y)
	{
		x=getf(x),y=getf(y);
		if(x!=y) fa[x]=y;
	}
};
bcj u;
struct xds{
	int a[200005];
	inline void upd(int id,int l,int r,int x,int y)
	{
		if(r<x||l>x) return;
		if(l==r){a[id]=y;return;}
		upd(ls,x,y),upd(rs,x,y);
		a[id]=a[id<<1]+a[id<<1|1];
	}
	inline int query(int id,int l,int r,int x,int y)
	{
		if(r<x||l>y) return 0;
		if(x<=l&&r<=y) return a[id];
		return query(ls,x,y)+query(rs,x,y);
	}
};
xds t;
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>p>>c;pp[0]=p;
	for(int i=0;i<=L;i++)
	{
		if(i>0) pp[i]=phi(pp[i-1])/*,cout<<pp[i]<<endl*/;
		else pp[i]=p;
		pw[i][0][0]=pw[i][1][0]=1%pp[i];
		for(int j=1;j<=65535;j++) pw[i][0][j]=pw[i][0][j-1]*c%pp[i];
		pw[i][1][1]=pw[i][0][65535]*c%pp[i];
		for(int j=2;j<=65535;j++) pw[i][1][j]=pw[i][1][j-1]*pw[i][1][1]%pp[i];
	}
//	cout<<solve(3,1,0);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i][0];
		t.upd(1,1,n,i,a[i][0]);
		for(int j=1;j<=L;j++) a[i][j]=solve(j,a[i][0],0);
	/*	cout<<i<<": ";
		for(int j=0;j<=L;j++) cout<<a[i][j]<<',';
		cout<<endl;*/
	}
	u.init(n+1);
	while(m--)
	{
		int opt,x,y;
		cin>>opt>>x>>y;
		if(opt==0)
		{
			for(int i=x;i<=y;i++)
			{
				i=u.getf(i);
				if(i>y) break;
				num[i]++;
				t.upd(1,1,n,i,a[i][num[i]]);
				if(num[i]==L) u.merge(i,i+1);
			}
		}
		else cout<<t.query(1,1,n,x,y)%p<<'\n';
	}
	return 0;
}/*4 4 2 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3*/