#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define TRACE 1
#define tcout TRACE && cout

#define IN(o) insert(o)

#define int long long

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1e5 + 10;

const int P = 571373;

int mod(int a)
{
	return a % P;
}

int add(int a, int b)
{
	a = mod(a);
	b = mod(b);
	return mod(a + b);
}

int mul(int a, int b)
{
	a = mod(a);
	b = mod(b);
	return mod(a * b);
}

int n, q;
int a[N];

#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l+r) >> 1)

struct Node
{
	int l, r, sz, x;
	int add, mul;
};

Node tr[N<<2];

void push_up(int rt)
{
	tr[rt].x = add(tr[lson].x, tr[rson].x);
}

void build(int rt, int l, int r)
{
	tr[rt] = {l, r, r - l + 1, 0, 0, 1};
	if(l == r)
	{
		tr[rt].x = mod(a[l]);
		return ;
	}
	build(lson, l, mid);
	build(rson, mid + 1, r);
	push_up(rt);
}

void push_down(int rt)
{
	tr[lson].x = add(mul(tr[rt].mul, tr[lson].x), mul(tr[rt].add, tr[lson].sz));
	tr[rson].x = add(mul(tr[rt].mul, tr[rson].x), mul(tr[rt].add, tr[rson].sz));
	tr[lson].add = add(tr[lson].add, tr[rt].add);
	tr[rson].add = add(tr[rson].add, tr[rt].add);
	tr[lson].mul = mul(tr[lson].mul, tr[rt].mul);
	tr[rson].mul = mul(tr[rson].mul, tr[rt].mul);
	tr[rt].mul = 1;
	tr[rt].add = 0;
}

void upd_add(int rt, int sp, int ep, int v)
{
	int l = tr[rt].l;
	int r = tr[rt].r;
	if(sp <= l && r <= ep)
	{
		tr[rt].add = add(tr[rt].add, v);
		tr[rt].x = add(tr[rt].x, mul(v, tr[rt].sz));
		return ;
	}
	push_down(rt);
	if(sp <= mid)
	{
		upd_add(lson, sp, ep, v);
	}
	if(ep > mid)
	{
		upd_add(rson, sp, ep, v);
	}
	push_up(rt);
}

void upd_mul(int rt, int sp, int ep, int v)
{
	int l = tr[rt].l;
	int r = tr[rt].r;
	if(sp <= l && r <= ep)
	{
		tr[rt].mul = mul(tr[rt].mul, v);
		tr[rt].add = mul(tr[rt].add, v);
		tr[rt].x = mul(tr[rt].x, v);
		return ;
	}
	push_down(rt);
	if(sp <= mid)
	{
		upd_mul(lson, sp, ep, v);
	}
	if(ep > mid)
	{
		upd_mul(rson, sp, ep, v);
	}
	push_up(rt);
}

int query(int rt, int sp, int ep)
{
	if(tr[rt].r == 0)
	{
		return 0;
	}
	int l = tr[rt].l;
	int r = tr[rt].r;
	if(sp <= l && r <= ep)
	{
		return tr[rt].x;
	}
	push_down(rt);
	int res = 0;
	if(ep <= mid)
	{
		return query(lson, sp, ep);
	}
	if(sp > mid)
	{
		return query(rson, sp, ep);
	}
	int L = query(lson, sp, ep);
	int R = query(rson, sp, ep);
	res = add(L, R);
	return mod(res);
}

#undef lson
#undef rson
#undef mid

signed main()
{
	fst;
	int l;
	cin >> n >> q >> l;
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
	}
	build(1, 1, n);
	for(int i=1; i<=q; i++)
	{
		int op, x, y, v;
		cin >> op >> x >> y;
		if(op == 3)
		{
			int res = query(1, x, y);
			cout << res << endl;
		}
		else
		{
			cin >> v;
			if(op == 1)
			{
				upd_mul(1, x, y, v);
			}
			else
			{
				upd_add(1, x, y, v);
			}
		}
	}
	return 0;
}