#include<iostream>
using namespace std;
#define N 100005
#define lc p>>1
#define rc p>>1|1
#define ll long long
#define M 571373
int n, q, m;
int w[N];
struct tr {
	int l;
	int r;
	ll sum;
	ll add;
	ll mult;
}tr[N * 4];
void pushdown(int p) {
	tr[lc].sum = (tr[lc].sum * tr[p].mult + tr[p].add * (tr[lc].r - tr[lc].l + 1))%M;
	tr[lc].mult = (tr[lc].mult * tr[p].mult) % M;
	tr[lc].add = (tr[lc].add * tr[p].mult + tr[p].add) % M;
	
	tr[rc].sum = (tr[rc].sum * tr[p].mult + tr[p].add * (tr[rc].r - tr[rc].l + 1))%M;
	tr[rc].mult = (tr[rc].mult * tr[p].mult) % M;
	tr[rc].add = (tr[rc].add * tr[p].mult + tr[p].add) % M;
	
}
void pushup(int p) {
	tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void build(int p, int l, int r) {
	if (l == r){
		tr[p] = { w[p]%M,l,r,0,1 };
		return;
	}
	int m = l + r >> 1;
	build(lc, l, m);
	build(rc, m + 1, r);
	pushup(p);
}
void update(int p, int x, int y, int k, int q) {
	if (x <= tr[p].l && tr[p].r >= y && q == 1)
	{
		tr[p].add = (tr[p].add * k) % M;
		tr[p].mult = (tr[p].mult * k) % M;
		tr[p].sum = (tr[p].sum * k) % M;
		return;
	}//乘法更新
	if (x <= tr[p].l && tr[p].r >= y && q == 2)
	{
		tr[p].add = (tr[p].add * k) % M;
		tr[p].sum = (tr[p].sum + (tr[p].r - tr[p].l + 1) * k);
		return;
	}//加法更新
	
	
	int m = tr[p].l + tr[p].r >> 1;
	pushdown(p);
	if (x <= m)update(lc, x, y, k, q);
	if (y > m)update(rc, x, y, k, p);
	pushup(p);

}
ll query(int p, int x, int y) {
	if (x <= tr[p].l && tr[p].r >= y)
		return tr[p].sum % M;
	int m = (tr[p].l + tr[p].r) >> 1;
	ll sum = 0;
	if (x <= m)sum += query(lc, x, y);
	if (y > m)sum += query(rc, x, y);
	return sum % M;
}//取数
int main() {

	cin >> n >> q >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> w[i];
	}
	build(1, 1, n);
	int h, x, y, k;
	for (int i = 0; i < q; i++) {
		cin >> h;
		if (h == 1 || h == 2)
		{
			cin >> x >> y >> k;
			update(1, x, y, k, h);
		}
		else if (h == 3)
		{
			cin >> x >> y;
			ll sum = query(1, x, y);
			cout << sum << endl;
		}
	}
}

不知道为什么总是输出负数，有关输出的地方都是longlong，实在不知道怎么回事了。