样例已过，码风良好

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 50, p = 571373;

int n, q, a[N], _;

struct node {
	int w;
	int add, mul;
} t[N * 4];

void maketag(int k, int l, int r, ll x, int op) {
	if (op == 1) {
		(t[k].add *= x) %= p;
		(t[k].mul *= x) %= p;
		(t[k].w *= x) %= p;
	} else {
		(t[k].add += x) %= p;
		(t[k].w += (r - l + 1) * x) %= p;
	}
}

void pushup(int k) {
	t[k].w = (t[k + k].w + t[k + k + 1].w) % p;
}

void pushdown(int k, int l, int r) {
	int m = (l + r) >> 1;
	maketag(k + k, l, m, t[k].mul, 1);
	maketag(k + k, l, m, t[k].add, 2);
	maketag(k + k + 1, m + 1, r, t[k].mul, 1);
	maketag(k + k + 1, m + 1, r, t[k].add, 2);
	t[k].add = 0, t[k].mul = 1;
}

void buildtree(int k, int l, int r) {
	t[k].add = 0, t[k].mul = 1;
	if (l == r) {
		t[k].w = a[l] % p;
		return;
	}
	int m = (l + r) >> 1;
	buildtree(k + k, l, m);
	buildtree(k + k + 1, m + 1, r);
	t[k].w = (t[k + k].w + t[k + k + 1].w) % p;
}

void add(int k, int l, int r, int x, int y, ll z) {
	if (l == x && r == y) {
		maketag(k, l, r, z, 2);
		return;
	}
	pushdown(k, l, r);
	int m = (l + r) >> 1;
	if (y <= m) add(k + k, l, m, x, y, z);
	else if (x > m) add(k + k + 1, m + 1, r, x, y, z);
	else add(k + k, l, m, x, m, z), add(k + k + 1, m + 1, r, m + 1, y, z);
	pushup(k);
}

void mul(int k, int l, int r, int x, int y, ll z) {
	if (l == x && r == y) {
		maketag(k, l, r, z, 1);
		return;
	}
	pushdown(k, l, r);
	int m = (l + r) >> 1;
	if (y <= m) mul(k + k, l, m, x, y, z);
	else if (x > m) mul(k + k + 1, m + 1, r, x, y, z);
	else mul(k + k, l, m, x, m, z), mul(k + k + 1, m + 1, r, m + 1, y, z);
	pushup(k);
}

int calc(int k, int l, int r, int x, int y) {
	if (l == x && r == y) 
		return t[k].w;
	pushdown(k, l, r);
	int m = (l + r) >> 1, cnt = 0;
	if (y <= m) cnt = calc(k + k, l, m, x, y);
	else if (x > m) cnt = calc(k + k + 1, m + 1, r, x, y);
	else cnt = calc(k + k, l, m, x, m) + calc(k + k + 1, m + 1, r, m + 1, y);
	pushup(k);
	return cnt;
}

int main() {
	scanf("%d%d%d", &n, &q, &_);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	buildtree(1, 1, n);
	for (; q--; ) {
		int op, x, y;
		ll k;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			scanf("%lld", &k);
			mul(1, 1, n, x, y, k);
		} else if (op == 2) {
			scanf("%lld", &k);
			add(1, 1, n, x, y, k);
		} else printf("%d\n", calc(1, 1, n, x, y));
	}
	return 0;
}