WA #3 和 #20，其他OJ都过了，不知道为什么

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <cmath>

using namespace std;

const int N = 50005;

unordered_map<int, int> mp;

inline int phi(int n) {
	if (mp[n]) return mp[n]; int ret = n, t = n;
	for (register int i = 2; i * i <= n; ++i) {
		if (n % i) continue;
		while (!(n % i)) n /= i;
		ret /= i; ret *= i - 1;
	} if (n > 1) ret /= n, ret *= n - 1;
	return mp[t] = ret;
}

int n, m, p, c, a[N], lazy[N], pos[N], L[N], R[N], sum[N], BL, tms[N], org[N], tag[N];

inline int calc(int &x, int t, int p) {
	if (!t) {
		if (x < p) return 0;
		x %= p; return 1;
	} if (p == 1) { if (x >= 1) { x = 0; return 1; } x = 0; return 0; }
	int tt = phi(p); if (calc(x, t - 1, tt)) x += tt;
	int ttt = 1, y = c, k = x; bool ret = 0;
	while (k) {
		if (k & 1) {
			if (1ll * ttt * y >= p) ret = 1;
			ttt = (1ll * ttt * y) % p;
		} k >>= 1;
		if (k && 1ll * y * y >= p) ret = 1;
		y = (1ll * y * y) % p;
	} x = ttt;
	return ret;
}

inline void modify(int i) {
	sum[pos[i]] -= a[i]; ++tms[i]; a[i] = org[i]; calc(a[i], tms[i], p); sum[pos[i]] += a[i];
	if (sum[pos[i]] >= p) sum[pos[i]] -= p; if (sum[pos[i]] < 0) sum[pos[i]] += p;
}

inline void solv(int i) {
	if (tag[i]) return ; 
	tag[i] = 1;
	for (register int j = L[i]; j <= R[i]; ++j) {
		int t = a[j]; modify(j); tag[i] &= (t == a[j]);
	}
}

inline int read() {
	register int s = 0; register char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
	return s;
}

int main() {
	mp[1] = 1;
	n = read(); m = read(); p = read(); c = read(); BL = sqrt(n / log2(n)) / 3; if (!BL) BL = 1;
	for (register int i = 1; i <= n; ++i) pos[i] = (i - 1) / BL + 1, L[i] = 0x3f3f3f3f, tms[i] = 0;
	for (register int i = 1; i <= n; ++i) a[i] = org[i] = read();
	for (register int i = 1; i <= n; ++i) {
		L[pos[i]] = L[pos[i]] < i ? L[pos[i]] : i;
		R[pos[i]] = i; sum[pos[i]] += a[i]; if (sum[pos[i]] >= p) sum[pos[i]] -= p;
	} int opt, l, r;
	while (m--) {
		opt = read(); l = read(); r = read();
		if (!opt) {
			if (pos[l] == pos[r]) {
				int t = pos[l];
				if (!tag[t]) {
					if (L[t] == l && R[t] == r) solv(t);
					else for (register int i = l; i <= r; ++i) modify(i);
				}
			} else {
				for (register int i = l; i < L[pos[l] + 1]; ++i) modify(i);
				for (register int i = pos[l] + 1; i < pos[r]; ++i) solv(i);
				for (register int i = L[pos[r]]; i <= r; ++i) modify(i);
			}
		} else {
			int ans = 0;
			if (pos[l] == pos[r]) {
				for (register int i = l; i <= r; ++i) {
					ans += a[i]; if (ans >= p) ans -= p;
				}
			} else {
				for (register int i = l; i < L[pos[l] + 1]; ++i) {
					ans += a[i]; if (ans >= p) ans -= p;
				}
				for (register int i = pos[l] + 1; i < pos[r]; ++i) {
					ans += sum[i]; if (ans >= p) ans -= p;
				}
				for (register int i = L[pos[r]]; i <= r; ++i) {
					ans += a[i]; if (ans >= p) ans -= p;
				}
			} printf("%d\n", ans);
		}
	}
	return 0;
}