不是常数问题。

#20, $p=3$，在 $60\sim 70$ 行 $TLE$。

#include <bits/stdc++.h>
using namespace std;

const int N = 500010, M = 10010, K = 100;
int n, m, p, c, len, L, TT;
int prime[M], vis[M], tot;
int a[N], phi[K], f[K][K], g[K][K], f2[N][K], g2[K], limit[K];
int cc[K][2 * M], cc2[K][2 * M], w[100];

inline int rd() {
	int f = 1, w = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + ch - 48; ch = getchar();}
	return f * w;
}

inline void write(int x) {
	if (x < 0) x = -x, putchar('-');
	if (x == 0) {
		putchar('0');
		return;
	}
	int t = 0;
	while (x) {w[++ t] = x % 10; x /= 10;}
	for (int i = t; i >= 1; i -- ) putchar(char('0' + w[i]));
}

int gcd(int a, int b) {
	return (b == 0) ? a : gcd(b, a % b);
}

inline int qpow(int a, int b, int mo) {
	if (c == 1) {
		if (1 >= phi[mo]) TT = 1; 
	} else if (b > limit[mo]) TT = 1;
	return 1ll * cc2[mo][b / L] * cc[mo][b % L] % phi[mo];
}

inline int get_phi(int x) {
	int ans = 1;
	for (int i = 1; i <= tot && prime[i] * prime[i] <= x; i ++ ) {
		if (x % prime[i] == 0) {
			int cnt = 1;
			while (x % prime[i] == 0) x /= prime[i], cnt *= prime[i];
			ans *= (cnt - cnt / prime[i]);
		}
	}
	if (x > 1) ans *= x - 1;
	return ans;
}

inline void prepare() {
	for (int i = 2; i <= 10000; i ++ ) {
		if (!vis[i]) prime[++ tot] = i;
		for (int j = 1; i * prime[j] <= 10000; j ++ ) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
	phi[0] = p;
	for (int i = 1; ; i ++ ) {
		phi[i] = get_phi(phi[i - 1]);
		if (phi[i] == 1) {
			len = i;
			break;
		}
	}
	phi[++ len] = 1;
	phi[len + 1] = 1;
	for (int k = 0; k <= len; k ++ ) g2[k] = gcd(phi[k], c);
	for (int i = 1; i <= n; i ++ )

	L = (int)sqrt(2 * p);
	for (int k = 0; k <= len; k ++ ) {
		cc[k][0] = cc2[k][0] = 1;
		for (int j = 1; j <= L; j ++ ) cc[k][j] = 1ll * cc[k][j - 1] * c % phi[k];
		for (int j = 1; j < L + 10; j ++ ) cc2[k][j] = 1ll * cc2[k][j - 1] * cc[k][L] % phi[k];
		if (c != 1){
			for (int j = 1, r = 1; ; j ++ ) {
				if (1ll * r * c < phi[k]) {
					limit[k] = j;
				} else break;
				r *= c;
			}
			if (limit[k] == 0) {
				if (1 >= phi[k]) limit[k] = -1;
			}
		}
	}
	for (int i = 1; i <= n; i ++ ) {
	    memset(f, 0, sizeof f);
	    memset(g, 0, sizeof f);
		for (int k = 0; k <= len; k ++ ) {
			f[0][k] = a[i] % phi[k];
			if (a[i] >= phi[k]) g[0][k] = 1;
		}	    
		for (int j = 1; j <= len; j ++ )
			for (int k = 0; k <= len; k ++ )
				if (g2[k] ^ 1) {
					TT = 0;
					f[j][k] = qpow(c, f[j - 1][k + 1] + (g[j - 1][k + 1] ? phi[k + 1] : 0), k);
					g[j][k] = TT;
				} else {
					TT = 0;
					f[j][k] = qpow(c, f[j - 1][k + 1], k);
					g[j][k] = TT;
				}
		for (int j = 0; j <= len; j ++ ) f2[i][j] = f[j][0];
	}
}

struct Node {
	int mn, v;
} tr[N << 2];

inline void pushup(int u) {
	tr[u].v = (tr[u << 1].v + tr[u << 1 | 1].v) % p;
}

void build(int u, int l, int r) {
	if (l == r) return tr[u].v = a[l], void();
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int l, int r, int s, int t) {
	if (tr[u].mn >= len) return;
	if (!(l ^ r)) {
		tr[u].mn ++ ;
		tr[u].v = f2[l][tr[u].mn];
		return;
	}
	int mid = l + r >> 1;
	if (s <= mid) modify(u << 1, l, mid, s, t);
	if (t > mid) modify(u << 1 | 1, mid + 1, r, s, t);
	pushup(u);
}

int query(int u, int l, int r, int s, int t) {
	if (s <= l && r <= t) return tr[u].v;
	int mid = l + r >> 1, res = 0;
	if (s <= mid) res = (res + query(u << 1, l, mid, s, t)) % p;
	if (t > mid) res = (res + query(u << 1 | 1, mid + 1, r, s, t)) % p;
	return res;
}


int main() {
    n = rd(), m = rd(), p = rd(), c = rd();
    for (int i = 1; i <= n; i ++ ) a[i] = rd();
    build(1, 1, n);
    prepare();
    for (int i = 1; i <= m; i ++ ) {
    	int op = rd(), l = rd(), r = rd();
    	if (op == 0) {
    		modify(1, 1, n, l, r);
		} else {
			write(query(1, 1, n, l, r));
			putchar('\n');
		}
	}
    return 0;
}