#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=55555;
long long n,m,c,p;
long long a[MAXN];
long long t[MAXN][30];
long long lim,phip[MAXN];
long long pow1[40][MAXN],pow2[40][MAXN];
const int R=20000;
int o,pow3[MAXN];
long long getPhi(long long x)
{
	long long res=x;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i)continue;
		res=res*(i-1)/i;
		while(x%i==0)x/=i;
	}
	if(x>1)
	{
		res=res*(x-1)/x;
	}
	return res;
}
long long qpow(long long a,long long k,long long p)
{
	if(!k)return 1;
	long long r=qpow(a,k/2,p);
	r=r*r%p;
	if(k&1)r=r*a%p;
	return r;
}
long long check(long long a,long long b,long long p)
{
	long long pp=phip[p];
	if(b<=o&&pow3[b]<pp)return pow3[b];
	return pow2[p][b/R]*pow1[p][b%R]%pp+pp;
}
long long tower(long long a,long long b,long long s)
{
	if(b==0)return a;
	return check(a,tower(a,b-1,s+1),s);
}
void init()
{
	int x=phip[0]=p;
	while(x>1)
	{
		x=getPhi(x);
		phip[++lim]=x;
	}
	phip[++lim]=1;
	for(int i=0;i<lim;i++)
	{
		int tmp=1;
		for(int j=0;j<=R;j++)
		{
			pow1[i][j]=tmp%phip[i];
			tmp=tmp*c%phip[i];
		}
	}
	for(int i=0;i<lim;i++)
	{
		int tmp=1;
		for(int j=0;j<=R;j++)
		{
			pow2[i][j]=tmp%phip[i];
			tmp=tmp*pow1[i][R]%phip[i];
		}
	}
	int tmp=1;
	for(int i=0;i<=R;i++)
	{
		pow3[i]=tmp;
		tmp=tmp*c;
		if(tmp>p)
		{
			o=i;
			break;
		}
	}
}
long long val[MAXN<<2],mn[MAXN<<2];
void pushup(int id)
{
	val[id]=val[id*2]+val[id*2+1];
	mn[id]=min(mn[id*2],mn[id*2+1]);
}
void build(int id,int l,int r)
{
	if(l==r)
	{
		val[id]=a[l];
		mn[id]=0;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	pushup(id);
}
void update(int id,int l,int r,int x,int y)
{
	if(mn[id]>=lim)return;
	if(y<l||r<x)return;
	if(l==r)
	{
		mn[id]++;
		val[id]=tower(a[l],mn[id],0)%p;
		return;
	}
	int mid=(l+r)/2;
	update(id*2,l,mid,x,y);
	update(id*2+1,mid+1,r,x,y);
	pushup(id);
}
int query(int id,int l,int r,int x,int y)
{
	if(y<l||r<x)return 0;
	if(x<=l&&r<=y)return val[id]%p;
	int mid=(l+r)/2;
	int res=(query(id*2,l,mid,x,y)+query(id*2+1,mid+1,r,x,y))%p;
	return res;
}
int main()
{
	//freopen("in.txt","r",stdin);
	cin>>n>>m>>p>>c;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	init();
	for(int i=1;i<=m;i++)
	{
		int op,l,r;
		cin>>op>>l>>r;
		if(op==0)
		{
			update(1,1,n,l,r);
		}
		if(op==1)
		{
			cout<<query(1,1,n,l,r)<<endl;
		}
	}
}