样例能过

#include <iostream>
#define ll long long
const int N = 1e5 + 5;
int n, m, p, a[N];
struct Node {
	ll sum, add, mul;
} tr[N << 2];
void pushdown(int o, int l, int r) {
	int mid = l + r >> 1;
	tr[o << 1].sum = (tr[o << 1].sum * tr[o].mul + tr[o].add * (mid - l + 1)) % p;
	tr[o << 1 | 1].sum = (tr[o << 1 | 1].sum * tr[o].mul + tr[o].add * (r - mid)) % p;
	tr[o << 1].mul = (tr[o << 1].mul * tr[o].mul) % p;
	tr[o << 1 | 1].mul = (tr[o << 1 | 1].mul * tr[o].mul) % p; 
	tr[o << 1].add = (tr[o << 1].add * tr[o].mul + tr[o].add) % p;
	tr[o << 1 | 1].add = (tr[o << 1 | 1].add * tr[o].mul + tr[o].add) % p;
	tr[o].add = 0, tr[o].mul = 1;
}
void pushup(int o) {
	tr[o].sum = tr[o << 1].sum + tr[o << 1 | 1].sum;
}
void build(int o, int l, int r) {
	tr[o].mul = 1;
	if (l == r) {
		tr[o].sum = a[l] % p;
		return;
	}
	int mid = l + r >> 1;
	build(o << 1, l, mid);
	build(o << 1 | 1, mid + 1, r);
	pushup(o);
}

void add(int o, int l, int r, int x, int y, int k) {
	if (x <= l && r <= y) {
		tr[o].sum = (tr[o].sum + (r - l + 1) * k) % p;
		tr[o].add = (tr[o].add + k) % p;
		return;
	}
	int mid = l + r >> 1;
	if (tr[o].add && l != r) pushdown(o, l, r);
	if (x <= mid) add(o << 1, l, mid, x, y, k);
	if (y > mid)  add(o << 1 | 1, mid + 1, r, x, y, k);
	pushup(o);
}
void mul(int o, int l, int r, int x, int y, int k) {
	if (x <= l && r <= y) {
		tr[o].sum = (tr[o].sum * k) % p;
		tr[o].mul = (tr[o].mul * k) % p;
		tr[o].add = (tr[o].add * k) % p;
		return;
	}
	int mid = l + r >> 1;
	if (tr[o].mul != 1 && l != r) pushdown(o, l, r);
	if (x <= mid) mul(o << 1, l, mid, x, y, k);
	if (y > mid)  mul(o << 1 | 1, mid + 1, r, x, y, k);
	pushup(o);
}
ll query(int o, int l, int r, int x, int y) {
	if (x <= l && r <= y) return tr[o].sum;
	int mid = l + r >> 1;
	if (tr[o].add || tr[o].mul != 1) pushdown(o, l, r);
	ll sum = 0;
	if (x <= mid) sum = (sum + query(o << 1, l, mid, x, y)) % p;
	if (y > mid)  sum = (sum + query(o << 1 | 1, mid + 1, r, x, y)) % p;
	return sum;
}
int main() {
	scanf("%d%d%d", &n, &m, &p);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	build(1, 1, n);
	while (m--) {
		int op, x, y;
		ll k;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			scanf("%lld", &k);
			k %= p;
			mul(1, 1, n, x, y, k);
		} else if (op == 2) {
			scanf("%lld", &k);
			k %= p;
			add(1, 1, n, x, y, k);
		} else if (op == 3) {
			printf("%lld\n", query(1, 1, n, x, y));
		}
	}
	return 0;
}