#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
const long long mod = 38;//571373
struct treenode;
using tnp = treenode*;
struct treenode {
	long long mul = 1;
	long long add = 0;
	tnp son[2];
	long long val = 0;
	inline void pushdown() {
		tnp s = son[0];
		s->add *= mul;
		s->mul *= mul;
		s->val *= mul;
		s->add += add;
		s->val *= mul;
		s->add %= mod;
		s->mul %= mod;
		s->val %= mod;
		s = son[1];
		s->add *= mul;
		s->mul *= mul;
		s->val *= mul;
		s->add += add;
		s->val *= mul;
		s->add %= mod;
		s->mul %= mod;
		s->val %= mod;
	}
	inline void update() {
		val = son[0]->val + son[1]->val ;
		while (val >= mod)val -= mod;
	}
	inline void mul_(long long x) {
		mul = ( mul * x ) % mod;
		val = ( val * x ) % mod;
	}
	inline void add_(long long x) {
		add = add + x ;
		val = val + x ;
		while (add >= mod)add -= mod;
		while (val >= mod)val -= mod;
	}
};
tnp pL, pR;
int Siz = 256;
void Create_New_Treenodes() {
	pL = (tnp)malloc( sizeof(treenode) * Siz );
	pR = pL + Siz;
	Siz <<= 1;
}
void Newp(tnp & x) {
	x = pL++;
	if (pL > pR)Create_New_Treenodes();
}
void Build(tnp cur, int l, int r, int * arr) {
	if (l == r) {
		cur->val = arr[l];
		return;
	}
	int m = (l + r) >> 1;
	Newp(cur->son[0]);
	Newp(cur->son[1]);
	Build(cur->son[0], l, m, arr);
	Build(cur->son[1], m + 1, r, arr);
	cur->update();
}
void Mul(tnp cur, int nl, int nr, int L, int R, int k) {
	int nm = (nl + nr) >> 1;
	if (R < nl || nr < L)return;
	if (L <= nl && nr <= R) {
		cur->mul_(k);
		return;
	}
	cur->pushdown();
	Mul(cur->son[0], nl, nm, L, R, k);
	Mul(cur->son[1], nm + 1, nr, L, R, k);
	cur->update();
}
void Add(tnp cur, int nl, int nr, int L, int R, int k) {
	int nm = (nl + nr) >> 1;
	if (R < nl || nr < L)return;
	if (L <= nl && nr <= R) {
		cur->add_(k);
		return;
	}
	cur->pushdown();
	Mul(cur->son[0], nl, nm, L, R, k);
	Mul(cur->son[1], nm + 1, nr, L, R, k);
	cur->update();
}
long long Query(tnp cur, int nl, int nr, int L, int R) {
	int nm = (nl + nr) >> 1;
	if (R < nl || nr < L)return 0;
	if (L <= nl && nr <= R) return cur->val;
	cur->pushdown();
	int ret = Query(cur->son[0], nl, nm, L, R) + Query(cur->son[1], nm + 1, nr, L, R);
	while (ret >= mod)ret -= mod;
	return ret;
}
int arr[maxn];
int main() {
	Create_New_Treenodes();
	tnp root;
	Newp(root);
	int n, m, opt, x, y;
	cin >> n >> m >> opt;
	for (int i = 1; i <= n; ++i)cin >> arr[i];
	Build(root, 1, n, arr);
	for (int i = 0; i < m; ++i) {
		cin >> opt >> x >> y;
		if (opt == 1) {
			cin >> opt;
			Mul(root, 1, n, x, y, opt);
		} else if (opt == 2) {
			cin >> opt;
			Add(root, 1, n, x, y, opt);
		} else if (opt == 3) {
			cout << Query(root, 1, n, x, y) << '\n';
		}
	}
	return 0;
}