#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef long long ll;
const int N = 100010;
const int mod = 571373;

struct Node {
	int l, r;
	int v;
	int tag1;//加
	int tag2;//乘
} tree[N * 4];
int num[N];
int n, m, p;

inline int size(int x)
{
	return tree[x].r - tree[x].l + 1;
}

inline void push_up(int x)
{
	tree[x].v = (tree[x << 1].v + tree[x << 1 | 1].v) % mod;
}

inline void push_down(int x)
{
	if (tree[x].tag1) {
		tree[x << 1].tag1 += tree[x].tag1;
		tree[x << 1 | 1].tag1 += tree[x].tag1;
		tree[x << 1].v = (tree[x << 1].v + tree[x].tag1 * size(x << 1) % mod) % mod;
		tree[x << 1].v = (tree[x << 1].v + tree[x].tag1 * size(x << 1 | 1) % mod) % mod;
		tree[x].tag1 = 0;
	}
	if (tree[x].tag2) {
		tree[x << 1].tag2 *= tree[x].tag2;
		tree[x << 1 | 1].tag2 *= tree[x].tag2;
		tree[x << 1].v = tree[x << 1].v * tree[x].tag2 % mod;
		tree[x << 1 | 1].v = tree[x << 1 | 1].v * tree[x].tag2 % mod;
		tree[x].tag2 = 0;
	}
}

void build(int x, int l, int r)
{
	tree[x].l = l, tree[x].r = r;
	if (l == r) {
		tree[x].v = num[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	push_up(x);
}

int query(int x, int l, int r)
{
	if (tree[x].l >= l && tree[x].r <= r) {
		return tree[x].v;
	}
	if (tree[x].l > r || tree[x].r < l) {
		return 0;
	}
	push_down(x);
	int ans = 0;
	if (tree[x << 1].r >= l) ans = (ans + query(x << 1, l, r) % mod) % mod;
	if (tree[x << 1 | 1].l <= r) ans = (ans + query(x << 1 | 1, l, r) % mod) % mod;
	return ans % mod;
}

void modify1(int x, int l, int r, int k)
{
	if (tree[x].l > r || tree[x].r < l) {
		return;
	}
	if (tree[x].l == tree[x].r) {
		tree[x].v = (tree[x].v + k * size(x) % mod) % mod;
		tree[x].tag1 = tree[x].tag1 + k;
		return;
	}
	push_down(x);
	if (tree[x << 1].r >= l) modify1(x << 1, l, r, k);
	if (tree[x << 1 | 1].l <= r) modify1(x << 1 | 1, l, r, k);
	push_up(x);
}

void modify2(int x, int l, int r, int k)
{
	if (tree[x].l > r || tree[x].r < l) {
		return;
	}
	if (tree[x].l == tree[x].r) {
		tree[x].v = (tree[x].v * k) % mod;
		tree[x].tag2 = tree[x].tag2 * k;
		return;
	}
	push_down(x);
	if (tree[x << 1].r >= l) modify2(x << 1, l, r, k);
	if (tree[x << 1 | 1].l <= r) modify2(x << 1 | 1, l, r, k);
	push_up(x);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
	}
	build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int op;
		cin >> op;
		if (op == 1) {
			int x, y, k;
			cin >> x >> y >> k;
			modify2(1, x, y, k);
		} else if (op == 2) {
			int x, y, k;
			cin >> x >> y >> k;
			modify1(1, x, y, k);
		} else if (op == 3) {
			int x, y;
			cin >> x >> y;
			cout << query(1, x, y) << endl;
		}
	}
	return 0;
}