1. #include <cstdio>
    2. #include <algorithm>
    3. #include <cstring>
    4. #include <cmath>
    5. #include <vector>
    6. #include <cstdlib>
    7. #include <iostream>
    8. #include <queue>
    9. using namespace std;
    10. #define ll long long
    11. #define For(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
    12. #define in(x) x = gi()
    13. inline int gi()
    14. {
    15.     char tmp = getchar();
    16.     int ans = 0;
    17.     while (!isdigit(tmp))
    18.         tmp = getchar();
    19.     while (isdigit(tmp))
    20.         ans = ans * 10 + tmp - '0', tmp = getchar();
    21.     return ans;
    22. }
    23. const int N = 1e5 + 10;
    24. #define LOG 58
    25. int n, m, p, c;
    26. int cntp;
    27. struct Seg
    28. {
    29.     int min, sum;
    30. } T[N << 2];
    32. #define ls (pos << 1)
    33. #define rs (ls | 1)
    34. #define mid ((l + r) >> 1)
    35. #define lson ls, l, mid
    36. #define rson rs, mid + 1, r
    37. inline void Pu(int pos)
    38. {
    39.     T[pos].min = min(T[ls].min, T[rs].min);
    40.     T[pos].sum = T[ls].sum + T[rs].sum;
    41.     while(T[pos].sum >= p) T[pos].sum -= p;
    42. }
    43. int A[LOG][N], Phi[N];
    44. void Update(int pos, int l, int r, int ql, int qr)
    45. {
    46.     if (T[pos].min >= cntp)
    47.         return;
    48.     if (l == r)
    49.     {
    50.         T[pos].min++;
    51.         T[pos].sum = A[T[pos].min][l];
    52.         return;
    53.     }
    54.     if (ql <= mid)
    55.         Update(lson, ql, qr);
    56.     if (qr > mid)
    57.         Update(rson, ql, qr);
    58.     Pu(pos);
    59. }
    60. int Query(int pos, int l, int r, int ql, int qr)
    61. {
    62.     if (ql <= l && r <= qr)
    63.     {
    64.         return T[pos].sum;
    65.     }
    66.     int ans = 0;
    67.     if (ql <= mid)
    68.         ans += Query(lson, ql, qr);
    69.     if (qr > mid)
    70.         ans = 1ll * (ans + Query(rson, ql, qr)) % p;
    71.     return ans % p;
    72. }
    73. inline int Get(int n)
    74. {
    75.     static int t, i, ans;
    76.     t = n, ans = n;
    77.     for (i = 2; i * i <= n; ++i)
    78.         if (t % i == 0)
    79.         {
    80.             while (!(t % i))
    81.                 t /= i;
    82.             ans = ans / i * (i - 1);
    83.         }
    84.     if (t > 1)
    85.         ans = ans / t * (t - 1);
    86.     return ans;
    87. }
    88. int Pow1[1<<16][LOG], Pow2[1<<16][LOG];
    89. inline int Mod(long long x, int p)
    90. {
    91.     if (x >= p)
    92.         return x % p +p ;
    93.     return x;
    94. }
    95. void Pre()
    96. {
    97.     For(i, 0, cntp)
    98.     {
    99.         Pow2[0][i] = Pow1[0][i] = 1;
    100.         For(j, 1, (1<<15)-1)
    101.             Pow1[j][i] = Mod(1ll * Pow1[j - 1][i] * c, Phi[i]);
    102.         Pow2[1][i] = Mod(1ll*Pow1[(1<<15)-1][i]*c,Phi[i]);
    103.         For(j, 2, (1<<15)-1)
    104.             Pow2[j][i] = Mod(1ll * Pow2[j - 1][i] * Pow2[1][i], Phi[i]);
    105.     }
    106.     return;
    107. }
    108. int Pow(int a, int b)
    109. {
    110.     int j = a & 32767, k = a >> 15;
    111.     return Mod(1ll * Pow1[j][b] * Pow2[k][b], Phi[b]);
    112. }
    113. int F(int x, int a, int b)
    114. {
    115.     if (!a)
    116.         return Mod(x, Phi[b]);
    117.     if (b == cntp)
    118.         return c ? 1 : 0;
    119.     return Pow(F(x, a - 1, b + 1), b);
    120. }
    121. void Build(int pos, int l, int r)
    122. {
    123.     if (l == r)
    124.     {
    125.         T[pos].min = 0;
    126.         T[pos].sum = A[0][l];
    127.         return;
    128.     }
    129.     Build(lson), Build(rson);
    130.     Pu(pos);
    131. }
    132. signed main()
    133. {
    134. #ifdef NICEGUODONG
    135.     freopen("data.in", "r", stdin);
    136. #endif
    137.     in(n), in(m), in(p), in(c);
    138.     Phi[0]=p;
    139.     while(Phi[cntp]>1){
    140.         int x=cntp;
    141.         Phi[++cntp]=Get(Phi[x]);
    142.     }
    143.     Phi[++cntp]=1;
    144.     Pre();
    145.     For(i, 1, n) A[0][i] = gi() ; // diff
    146.     For(i, 1, n){
    147.         For(j, 1, cntp+1)
    148.             A[j][i] = F(A[0][i], j, 0) % p;
    149.         A[0][i] %= p;    
    150.     }
    151.     Build(1, 1, n);
    152.     // return 0;
    153.     For(i, 1, m)
    154.     {
    155.         int opt, l, r;
    156.         in(opt), in(l), in(r);
    157.         if (opt == 0)
    158.             Update(1, 1, n, l, r);
    159.         if (opt == 1)
    160.         {
    161.             cout << (Query(1, 1, n, l, r)) % p;
    162.             putchar('\n');
    163.         }
    164.     }
    165.     return 0;
    166. }