https://www.luogu.com.cn/record/92789432

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll n, q, opt, mod, l, r, k, a[N], sum[N << 2], tag[N << 2], mul[N << 2];
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void push_up(int p) {
	sum[p] = sum[ls(p)] + sum[rs(p)];
}
void build(int p, int l, int r) {
	if (l == r) { sum[p] = a[l]; return; }
	int mid = (l + r) >> 1;
	mul[p] = 1;
	build(ls(p), l, mid), build(rs(p), mid + 1, r);
	push_up(p);
}
inline void push_tag(int p, int l, int r, int fa) {
	mul[p] *= mul[fa], sum[p] *= mul[fa];
	tag[p] += tag[fa], sum[p] += (r - l + 1) * tag[fa];
	mul[p] %= mod, tag[p] %= mod, sum[p] %= mod; 
}
inline void push_down(int p, int l, int r) {
	int mid = (l + r) >> 1;
	push_tag(ls(p), l, mid, p);
	push_tag(rs(p), mid + 1, r, p);
	tag[p] = 0;
}
void modify(int p, int nl, int nr, int l, int r, ll k) {
	if (nl <= l && r <= nr) { 
		tag[p] += k, sum[p] += (r - l + 1) * k;
		tag[p] %= mod, sum[p] %= mod;
		return;
	}
	push_down(p, l, r);
	int mid = (l + r) >> 1;
	if (nl <= mid) modify(ls(p), nl, nr, l, mid, k);
	if (nr > mid) modify(rs(p), nl, nr, mid + 1, r, k);
	push_up(p);
}
void multip(int p, int nl, int nr, int l, int r, ll k) {
	if (nl <= l && r <= nr) {
		mul[p] *= k, tag[p] *= k, sum[p] *= k;
		mul[p] %= mod, tag[p] %= mod, sum[p] %= mod;
		return;
	}
	push_down(p, l, r);
	int mid = (l + r) >> 1;
	if (nl <= mid) multip(ls(p), nl, nr, l, mid, k);
	if (nr > mid) multip(rs(p), nl, nr, mid + 1, r, k);
	push_up(p);
}
ll query(int p, int nl, int nr, int l, int r) {
	ll res = 0;
	if (nl <= l && r <= nr) return sum[p];
	push_down(p, l, r);
	int mid = (l + r) >> 1;
	if (nl <= mid) res += query(ls(p), nl, nr, l, mid);
	if (nr > mid) res += query(rs(p), nl, nr, mid + 1, r);
	return res % mod;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> q >> mod;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= q; i ++) {
		cin >> opt >> l >> r;
		if (opt == 1) cin >> k, multip(1, l, r, 1, n, k);
		else if (opt == 2) cin >> k, modify(1, l, r, 1, n, k);
		else cout << query(1, l, r, 1, n) << '\n';
//		for (int i = 1; i <= n; i ++)
//			cout << query(1, i, i, 1, n) << ' ';
//		cout << '\n';
	}
	return 0;
}