#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<bitset>
using namespace std;
typedef long long ll;
ll n,m,p,c;
inline void readl(ll &x){
    x=0;
    char ch=getchar_unlocked();
    while(!isdigit(ch)){
        ch=getchar_unlocked();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar_unlocked();
    }
    return;
}
inline ll calc_phi(ll n){
    ll ans=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1){
        ans=ans/n*(n-1);
    }
    return ans;
}
ll phi[100];
int maxt=0;
inline void Init(){
    phi[0]=p;
    while(phi[maxt]>1){
        maxt++;
        phi[maxt]=calc_phi(phi[maxt-1]);
    }
    phi[++maxt]=1;
    return;
}
bool flag=0;
inline ll ksm(ll a,ll b,ll p){
    flag=0;
    ll ans=1;
    if(a>=p){
        a%=p;
    }
    while(b){
        if(b&1){
            ans*=a;
            if(ans>=p){
                flag=1;
                ans%=p;
            }
        }
        a*=a;
        if(a>=p){
            a%=p;
        }
        b>>=1;
    }
    return ans;
}
ll dfs(ll k,int dep,int mdep){
    flag=0;
    if(dep==mdep){
        if(k>=phi[dep]){
            flag=1;
            k%=phi[dep];
        }
        return k;
    }
    ll t=dfs(k,dep+1,mdep);
    return ksm(c,flag?t+phi[dep+1]:t,phi[dep]);
}
ll a[50010];
struct node{
    ll val;
    int mint;
    node(){
        val=0;
        mint=0;
    }
}tree[50010<<2];
inline void pushup(int u){
    tree[u].val=tree[u<<1].val+tree[u<<1|1].val;
    if(tree[u].val>=p){
        tree[u].val-=p;
    }
    tree[u].mint=min(tree[u<<1].mint,tree[u<<1|1].mint);
    return;
}
void build(int l,int r,int u){
    if(l==r){
        tree[u].val=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    pushup(u);
    return;
}
void update(int l,int r,int L,int R,int u){
    if(tree[u].mint>=maxt){
        return;
    }
    if(L==R){
        tree[u].mint++;
        tree[u].val=dfs(a[L],0,tree[u].mint);
        return;
    }
    int mid=(L+R)>>1;
    if(l<=mid&&tree[u<<1].mint<maxt){
        update(l,r,L,mid,u<<1);
    }
    if(mid<r&&tree[u<<1|1].mint<maxt){
        update(l,r,mid+1,R,u<<1|1);
    }
    pushup(u);
    return;
}
ll query(int l,int r,int L,int R,int u){
    if(l<=L&&R<=r){
        return tree[u].val;
    }
    int mid=(L+R)>>1;
    ll ans=0;
    if(l<=mid){
        ans+=query(l,r,L,mid,u<<1);
    }
    if(mid<r){
        ans+=query(l,r,mid+1,R,u<<1|1);
    }
    if(ans>=p){
        ans-=p;
    }
    return ans;
}
int main(){
    readl(n);readl(m);readl(p);readl(c);
    Init();
    for(int i=1;i<=n;i++){
        readl(a[i]);
    }
    build(1,n,1);
    while(m--){
        ll op,l,r;
        readl(op);
        readl(l);
        readl(r);
        if(op==0){
            update(l,r,1,n,1);
        }else{
            cout<<query(l,r,1,n,1)<<endl;
        }
    }
    return 0;
}