释义：在少量代码中创造大量错误

#include <bits/stdc++.h>
using namespace std;

#define ll long long

#ifdef ONLINE_JUDGE
	#define mod 571373
#else
	#define mod 38
#endif

struct node {
	ll mul, add, sum;
	ll l, r;
} tree[400040];

ll a[100010];

void pushup (ll p) {
	tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum % mod;
}

void build (ll p, ll pl, ll pr) {
	tree[p].mul = 1, tree[p].l = pl, tree[p].r = pr;
	if (pl == pr) {
		tree[p].sum = a[p];
		return;
	}
	ll mid = tree[p].l + ((tree[p].r - tree[p].l)>> 1);
	if (pl <= mid)
		build (p << 1, pl, mid);
	if (pr > mid)
		build (p << 1 | 1, mid + 1, pr);
	pushup(p);
}

void pushdown (ll p) {
	ll ls = p << 1;
	ll rs = ls | 1;
	tree[ls].sum = tree[ls].sum * tree[p].mul % mod;
	tree[rs].sum = tree[rs].sum * tree[p].mul % mod;
	tree[ls].sum += tree[ls].add * (tree[ls].r - tree[ls].l + 1) % mod;
	tree[rs].sum += tree[rs].add * (tree[rs].r - tree[rs].l + 1) % mod;
	tree[ls].mul = tree[ls].mul * tree[p].mul % mod;
	tree[rs].mul = tree[rs].mul * tree[p].mul % mod;
	tree[ls].add = tree[ls].add * tree[p].mul + tree[p].add % mod;
	tree[rs].add = tree[rs].add * tree[p].mul + tree[p].add % mod;
	tree[p].add = 0;
	tree[p].mul = 1;
}

void addeach (ll p, ll l, ll r, ll k) {
	if (tree[p].l >= l && tree[p].r <= r) {
		tree[p].add += k % mod;
		tree[p].add %= mod;
		tree[p].sum += k * (tree[p].r - tree[p].l + 1) % mod;
		return;
	}
	pushdown(p);
	pushup(p);
	ll mid = l + ((r - l) >> 1);
	if (l <= mid)
		addeach(p << 1, l, mid, k);
	if (r > mid)
		addeach(p << 1 | 1, mid + 1, r, k);
	pushup(p);
}

void muleach (ll p, ll l, ll r, ll k) {
	if (tree[p].l >= l && tree[p].r <= r) {
		tree[p].add *= k % mod;
		tree[p].add %= mod;
		tree[p].mul *= k % mod;
		tree[p].mul %= mod;
		tree[p].sum += tree[p].sum * (k % mod);
		tree[p].sum %= mod;
		return;
	}
	pushdown(p);
	pushup(p);
	ll mid = l + ((r - l) >> 1);
	if (l <= mid)
		muleach(p << 1, l, mid, k);
	if (r > mid)
		muleach(p << 1 | 1, mid + 1, r, k);
	pushup(p);
}

ll getsum (ll p, ll l, ll r) {
	if (tree[p].l >= l && tree[p].r <= r) {
		return tree[p].sum % mod;
	}
	pushdown(p);
	ll mid = tree[p].l + ((tree[p].r - tree[p].l) >> 1);
	ll val = 0;
	if (l <= mid)
		val += getsum(p << 1, l, mid) % mod;
	if (r > mid)
		val += getsum(p << 1 | 1, mid + 1, r) % mod;
	return val % mod;
}

ll n, m, p, o, x, y, k;

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(nullptr);
	cin >> n >> m >> p;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	build(1, 1, n);
	while (m--) {
		cin >> o;
		if (o == 1){
			cin >> x >> y >> k;
			muleach(1, x, y, k);
		}
		else if (o == 2) {
			cin >> x >> y >> k;
			addeach(1, x, y, k);
		}else {
			cin >> x >> y;
			cout << getsum(1, x, y) << '\n';
		}
	}
	return 0;
}