#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

int n, m, cnt;

ll p, c;

ll phi[N], table[N];

namespace seg // n^x = n^(x % phi[x] + phi[x])

{

    struct data {

        ll ans, mn;

    } tree[N << ];

    inline ll getphi(ll x)

    {

        ll ret = x, lim = x;

        for(ll i = ; i * i <= lim; ++i) if(x % i == )

        {

            ret = ret * (i - ) / i;

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

        }

//      printf("ret=%d\n", ret);

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

        return ret;

    }

    inline ll power(ll x, ll t, ll p, bool &flag)

    {

        bool big = false;

        ll ret = ;

        for(; t; t >>= )

        {

            if(t & )

            {

                ret = ret * x ;

                flag |= big | (ret >= p);

                ret %= p;

            }

            x = x * x; if(x >= p) big = true, x %= p;

        }

        return ret;

    }

    ll calc(ll x, int t)

    {

        if(x >= phi[t]) x = x % phi[t] + phi[t];

        for(int i = t - ; i >= ; --i)

        {

            bool flag = false;

            x = power(c, x, phi[i], flag);

            if(flag) x += phi[i];

        }

        return x % phi[];

    }

    inline void build(int l, int r, int x)

    {

        if(l == r) {

            tree[x].ans = table[l];

            return;

        }

        int mid = (l + r) >> ;

        build(l, mid, x << );

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

        tree[x].ans = (tree[x << ].ans

                     + tree[x <<  | ].ans) % phi[];

    }

    inline void update(int l, int r, int x, int a, int b)

    { //如果这次的幂和上次一样就不变了

        if(tree[x].mn >= cnt) return;

        if(l > b || r < a) return;

        if(l == r)

        {

            ++tree[x].mn;

            tree[x].ans = calc(table[l], tree[x].mn);

            return;

        }

        int mid = (l + r) >> ;

        update(l, mid, x << , a, b);

        update(mid + , r, x <<  | , a, b);

        tree[x].mn = min(tree[x << ].mn,

                         tree[x <<  | ].mn);

        tree[x].ans = (tree[x << ].ans +

                       tree[x <<  | ].ans) % phi[];

    }

    inline ll query(int l, int r, int x, int a, int b)

    {

        if(l > b || r < a) return ;

        if(l >= a && r <= b) return tree[x].ans % phi[];

        int mid = (l + r) >> , ret = ;

        ret = (ret + query(l, mid, x << , a, b)) % phi[];

        ret = (ret + query(mid + , r, x <<  | , a, b)) % phi[];

        return ret;

    }

} using namespace seg;

int main()

{

    scanf("%d%d%lld%lld", &n, &m, &p, &c);

    phi[] = p;

    ll P = p;

    while(P != ) phi[++cnt] = P = getphi(P);

    phi[++cnt] = ;

    for(int i = ; i <= n; ++i) scanf("%lld", &table[i]);

    build(, n, );

    while(m--)

    {

        int opt, l, r; scanf("%d", &opt);

        if(opt == )

        {

            scanf("%d%d", &l, &r);

            update(, n, , l, r);

        }

        if(opt == )

        {

            scanf("%d%d", &l, &r);

            printf("%lld\n", query(, n, , l, r));

        }

    }

    return ;

}