#include<cmath>

#include<cstdio>

#include<iostream>

using namespace std;

#define N 50001

int n,m,p,c;

int a[N];

int sum[N<<];

int tag[N<<];

int lim,pi[],phi[];

int ans;

bool flag;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

int Pow(int a,int b,int mod)

{

    int res=;

    while(b)

    {

        if(b&)

        {

            if(1LL*res*a>=mod) flag=true;

            res=1LL*res*a%mod;

        }

        if(1LL*a*a>=mod) flag=true;

        a=1LL*a*a%mod;

        b>>=;

    }

    return res;

}

void build(int k,int l,int r)

{

    if(l==r)

    {

        sum[k]=a[l];

        return;

    }

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    sum[k]=(sum[k<<]+sum[k<<|])%p;

}

int get_phi(int x)

{

    int y=sqrt(x);

    int ph=x;

    for(int i=;i<=y;++i)

        if(!(x%i))

        {

            while(!(x%i)) x/=i;

            ph=ph/i*(i-);

        }

    if(x>) ph=ph/x*(x-);

    return ph;

}

int f(int dep,int x)

{

    int tmp=x;

    if(tmp>=phi[dep]) tmp=tmp%phi[dep]+phi[dep];

    for(int i=dep;i;--i)

    {

        flag=false;

        tmp=Pow(c,tmp,pi[i]);

        if(flag) tmp+=phi[i-];

    }

    return tmp;

}

void change(int k,int l,int r,int opl,int opr)

{

    if(tag[k]>=lim) return;

    if(l==r)

    {

        tag[k]++;

        sum[k]=f(tag[k],a[l]);

        return;

    }

    int mid=l+r>>;

    if(opl<=mid) change(k<<,l,mid,opl,opr);

    if(opr>mid) change(k<<|,mid+,r,opl,opr);

    tag[k]=min(tag[k<<],tag[k<<|]);

    sum[k]=(sum[k<<]+sum[k<<|])%p;

}

void query(int k,int l,int r,int opl,int opr)

{

    if(l>=opl && r<=opr)

    {

        ans+=sum[k];

        ans%=p;

        return;

    }

    int mid=l+r>>;

    if(opl<=mid) query(k<<,l,mid,opl,opr);

    if(opr>mid) query(k<<|,mid+,r,opl,opr);

}

int main()

{

    read(n); read(m); read(p); read(c);

    for(int i=;i<=n;++i) read(a[i]);

    build(,,n);

    int tmp=p;

    while(pi[lim]!=)

    {

        pi[++lim]=tmp;

        phi[lim]=get_phi(tmp);

        tmp=phi[lim];

    }

    int ty,l,r;

    while(m--)

    {

        read(ty); read(l); read(r);

        if(!ty) change(,,n,l,r);

        else

        {

            ans=;

            query(,,n,l,r);

            printf("%d\n",ans);

        }

    }

    return ;

}