#include<bits/stdc++.h>
using namespace std;
#define int long long
int getphi(int x)
{
    int res=x;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0)x=x/i;
        }
    if(x>1)res=res/x*(x-1);
    return res;
}
int n,q,p,c,op,x,y;
int d[100],v[2][100][1<<15],a[50005],cnt;
bool h[2][100][1<<15];
pair<int,bool> qpow(int x,int i){return {1LL*v[0][i][x&32767]*v[1][i][x>>15]%d[i],h[0][i][x&32767]||h[1][i][x>>15]||1LL*v[0][i][x&32767]*v[0][i][x>>15]>=d[i]};}
pair<int,bool> solve(int a,int k,int p=1)
{
	if(d[p]==1)return {0,1};
	if(k==0)return {a%d[p],a>=d[p]};
	pair<int,bool> tmp=solve(a,k-1,p+1);
	return qpow(tmp.first+d[p+1]*tmp.second,p);
}
#define mid (l+r)/2
template<class T,int N>
class tree
{
	T v[N<<4],minn[N<<4],init[N+5];
	void build(int l=1,int r=N,int rt=1)
	{
		if(l==r)return v[rt]=init[l],void();
		build(l,mid,rt*2),build(mid+1,r,rt*2+1);
		v[rt]=(v[rt*2]+v[rt*2+1])%p;
	}
	public:void updata(int x,int y,int l=1,int r=N,int rt=1)
	{
		if(r<x||y<l||minn[rt]==INT_MAX)return;
		if(l==r)
		{
			int u=solve(init[l],++minn[rt]).first;
			return (u==v[rt]?minn[rt]=INT_MAX:v[rt]=u),void();
		}
		updata(x,y,l,mid,rt*2),updata(x,y,mid+1,r,rt*2+1);
		v[rt]=(v[rt*2]+v[rt*2+1])%p;
		minn[rt]=min(minn[rt*2],minn[rt*2+1]);
	} 
	T getans(int x,int y,int l=1,int r=N,int rt=1)
	{
		if(r<x||y<l)return 0;
		if(x<=l&&r<=y)return v[rt];
		return (getans(x,y,l,mid,rt*2)+getans(x,y,mid+1,r,rt*2+1))%p;
	}
	tree(){}
	tree(T a[]){memcpy(init,a,sizeof init);build();}
};
#undef mid
tree<int,50000>t;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>p>>c;
	d[++cnt]=p;
	while(p>1)p=getphi(p),d[++cnt]=p;
	p=d[1];
	for(int i=1;i<=cnt;i++)
	{
		v[0][i][0]=1;
		for(int j=1;j<(1<<15);j++)v[0][i][j]=1LL*v[0][i][j-1]*c%d[i],h[0][i][j]=h[0][i][j-1]||(1LL*v[0][i][j-1]*c>=d[i]);
		v[1][i][0]=1;
		for(int j=1;j<(1<<15);j++)v[1][i][j]=1LL*v[1][i][j-1]*c*v[0][i][(1<<15)-1]%d[i],h[1][i][j]=h[1][i][j-1]||(1LL*v[1][i][j-1]*c*v[0][i][(1<<15)-1]>=d[i]);
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	t=*new tree<int,50000>(a);
	while(q--&&cin>>op>>x>>y)
		if(op)cout<<t.getans(x,y)<<endl;
		else t.updata(x,y);
	return 0;
}