#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int MOD = 571373;
int n, q, m;
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int a[N];
long long tree[N << 2], add[N << 2], mul[N << 2];
void push_up(int p) {
	tree[p] = (tree[ls(p)] + tree[rs(p)]) % MOD;
}
void add_tag(int p, int pl, int pr, int ad, int mu) {
    if (mu != 1) {
        tree[p] *= mu;
        add[p] *= mu, mul[p] *= mu;
        tree[p] %= MOD, add[p] %= MOD, mul[p] %= MOD;
    }
	if (ad != 0) {
		tree[p] += (pr - pl + 1) * ad;
		add[p] += ad;
		tree[p] %= MOD, add[p] %= MOD;
	}
}
void build(int p, int pl, int pr) {
	add[p] = 0, mul[p] = 1;
	if (pl == pr) {
		tree[p] = a[pl];
		return;
	}
	int mid = (pl + pr) >> 1;
	build(ls(p), pl, mid);
	build(rs(p), mid+1, pr);
	push_up(p);
}
void push_down(int p, int pl, int pr) {
	int mid = (pl + pr) >> 1;
    if (mul[p] != 1) {
        add_tag(ls(p), pl, mid, 0, mul[p]);
        add_tag(rs(p), mid+1, pr, 0, mul[p]);
        mul[p] = 1;
    }
	if (add[p] != 0) {
		add_tag(ls(p), pl, mid, add[p], 1);
		add_tag(rs(p), mid+1, pr, add[p], 1);
		add[p] = 0;
	}
}
void update(int p, int pl, int pr, int L, int R, int ad, int mu) {
	if (L <= pl && pr <= R) {
		add_tag(p, pl, pr, ad, mu);
		return;
	}
	push_down(p, pl, pr);
	int mid = (pl + pr) >> 1;
	if (L <= mid) update(ls(p), pl, mid, L, R, ad, mu);
	if (R >= mid+1) update(rs(p), mid+1, pr, L, R, ad, mu);
	push_up(p);
}
long long query(int p, int pl, int pr, int L, int R) {
	if (L <= pl && pr <= R) return tree[p];
	push_down(p, pl, pr);
	int mid = (pl + pr) >> 1;
	long long res = 0;
	if (L <= mid) res += query(ls(p), pl, mid, L, R);
	if (R >= mid+1) res += query(rs(p), mid+1, pr, L, R);
	return res % MOD;
}

int main() {
	scanf("%d %d %d", &n, &q, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	build(1, 1, n);
	while (q--) {
		int op, x, y, k;
		scanf("%d %d %d", &op, &x, &y);
		if (op == 1 || op == 2) scanf("%d", &k);
        k %= m;
		if (op == 1) {
			update(1, 1, n, x, y, 0, k);
		} else if (op == 2) {
			update(1, 1, n, x, y, k, 1);
		} else {
			printf("%lld\n", query(1, 1, n, x, y));
		}
	}
	return 0;
}