#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 5e4+10,M = N<<2;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}


int n,m,mx;
ll mod,c,a[N],s[N];
int p[1000010],phi[1000010],cnt;
bool v[1000010];
void prework(){
    phi[1] = 1;
    for(int i = 2;i <= 1e6;i++){
        if(!v[i])p[++cnt] = i,phi[i] = i-1;
        for(int j = 1;p[j] <= 1e6 / i;j++){
            v[i * p[j]] = 1;
            if(i % p[j] == 0){phi[i * p[j]] = phi[i] * p[j];break;}
            else phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
//    for(int i = 1;i <= 20;i++)cout<<phi[i]<<' ';
//    cout<<endl; 
}
ll get(ll x){
    if(x <= 1e6)return phi[x];
    ll ans = x;
    for(int i = 2;i <= sqrt(x);i++){
        if(x % i == 0){
            ans = ans / i * (i-1ll);
            while(x % i == 0)x /= i;
        }
    } 
    if(x > 1)ans = ans / x * (x-1);
    return ans;
}


ll ksm(ll x,ll y,ll mod,bool &flag){
    ll ans = 1;
    while(y){
        if(y & 1){
            if(ans * x >= mod)flag = 1;
            ans = ans * x % mod;
        }
        if(x * x >= mod)flag = 1;
        x = x * x % mod,y >>= 1;
    }return ans;
}

struct segment{
    ll sum[M],la[M];
    void pushup(int p){sum[p] = (sum[p<<1] + sum[p<<1|1]) % mod,la[p] = min(la[p<<1],la[p<<1|1]);}
    void build(int p,int l,int r){
        if(l == r)return sum[p] = a[l] %= mod,void();
        int mid = l + r >> 1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
        pushup(p);
    }
    ll find(ll x,int num){
        ll zhi = x;
        if(zhi >= s[num])zhi = x % s[num] + s[num];
        for(;num > 0;num--){
            bool flag = 0;
            zhi = ksm(c,zhi,s[num-1],flag);
            if(flag)zhi += s[num-1];
        }
        return zhi % mod;
    }
    void modify(int p,int l,int r,int L,int R){
        if(la[p] >= mx)return;
        if(l == r)return sum[p] = find(a[l],++la[p]),void();
        int mid = l + r >> 1;
        if(L <= mid)modify(p<<1,l,mid,L,R);
        if(R > mid)modify(p<<1|1,mid+1,r,L,R);
        pushup(p);
    }
    ll ask(int p,int l,int r,int L,int R){
        if(L <= l && r <= R)return sum[p];
        int mid = l + r >> 1;
        if(R <= mid)return ask(p<<1,l,mid,L,R);
        else if(L > mid)return ask(p<<1|1,mid+1,r,L,R);
        else return (ask(p<<1,l,mid,L,R) + ask(p<<1|1,mid+1,r,L,R)) % mod;
    }
}t;


void find(ll x){
    s[++mx] = x;
    if(x == 1)return;
    find(get(x));
}
int main(){
    freopen("verbinden.in","r",stdin);
    freopen("verbinden.out","w",stdout);
    n = read(),m = read(),mod = read(),c = read();
    prework();
    for(int i = 1;i <= n;i++)a[i] = read();
    mx = -1;
    find(mod);
    t.build(1,1,n);
    for(int i = 1;i <= m;i++){
        int op = read(),l = read(),r = read();
        if(!op)t.modify(1,1,n,l,r);
        else printf("%lld\n",t.ask(1,1,n,l,r));
    }
    
    
    return 0;
    
}