#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n;++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef array<int, 3> ai3;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 998244353;
const int inv2 = (Mod+1) / 2;
const int inv6 = (Mod+1) / 6;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, int p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 100100;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
}
int binom(int n, int m){ return mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(ll &a, ll b){ (b>a) ? (a=b) : 0; }

int n, q;
int a[111];

int C2(int x){ return (int)(1ll * x * (x-1) / 2 % Mod); }
int C3(int x){ return (int)(1ll * x * (x-1) % Mod * (x-2) % Mod * inv6 % Mod); }

int val[4][111];
void getval(int p){
	//cout << "-------------" << p << "---------------\n";
	val[0][p] = pw2[p+1];
	int sum = 0;
	for(int i = p; i >= 0; --i){
		val[1][p] = mul(pw2[p], a[i]);
		uadd(val[2][p], mul(C2(pw2[p]), mul(a[i], a[i])));
		uadd(sum, mul(a[i], mul(a[i], a[i])));
	}
	//cout << sum << " * " << C3(pw2[p]) << "\n";
	uadd(val[3][p], mul(C3(pw2[p]), sum));
	if(p >= 1){
		int coef22 = sub(pw2[2*p], pw2[p-1]);
		int coef32 = 0;
		uadd(coef32, mul(3, mul(C2(pw2[p-1]), pw2[p-1])));
		uadd(coef32, C3(pw2[p-1]));
		sum = 0;
		for(int i = p; i >= 0; --i) for(int j = i-1; j >= 0; --j){
			uadd(val[2][p], mul(coef22, mul(a[i], a[j])));
			uadd(sum, add(mul(mul(a[i], a[i]), a[j]), mul(mul(a[i], a[j]), a[j])));
		}
		//cout << sum << " * " << coef32 << "\n";
		uadd(val[3][p], mul(coef32, sum));
		if(p >= 2){
			int coef33 = 0;
			uadd(coef33, mul(42, pw2[3*(p-2)]));
			uadd(coef33, mul(21, mul(C2(pw2[p-2]), pw2[p-2])));
			uadd(coef33, C3(pw2[p-2]));
			sum = 0;
			for(int i = p; i >= 0; --i) for(int j = i-1; j >= 0; --j){ 
				int v = mul(coef33, mul(a[i], a[j]));
				for(int k = j-1; k >= 0; --k){
					uadd(val[3][p], mul(v, a[k]));
					uadd(sum, mul(a[i], mul(a[j], a[k])));
				}
			}
			//cout << sum << " * " << coef33 << "\n";
		}
	}
}

struct nod{
	array<int, 4> s;
	nod(int s0 = 1, int s1 = 0, int s2 = 0, int s3 = 0){ s[0] = s0, s[1] = s1, s[2] = s2, s[3] = s3; }
	void pushtag(int x){
		uadd(s[3], add(mul(C2(sub(s[0], 1)), mul(s[1], x)), add(mul(sub(s[0], 2), mul(s[2], x)), mul(C3(s[0]), mul(mul(x, x), x)))));
		uadd(s[2], add(mul(s[1], x), mul(C2(s[0]), mul(x, x))));
		uadd(s[1], mul(s[0], x));
	}
};
nod nodmrg(nod lh, nod rh){
	return nod(add(lh.s[0], rh.s[0]), add(lh.s[1], rh.s[1]), add(add(lh.s[2], rh.s[2]), mul(lh.s[1], rh.s[1])), add(add(lh.s[3], rh.s[3]), add(mul(lh.s[2], rh.s[1]), mul(lh.s[1], rh.s[2]))) );
}
int ch[2][20000200], tag[20000200], cn = 1;
nod dat[20000200];
int newnod(int lvl){
	if(!lvl) dat[cn] = nod();
	else dat[cn] = nod(val[0][lvl-1], val[1][lvl-1], val[2][lvl-1], val[3][lvl-1]);
	return cn++;
}
void pushtag(int u, int x){
	//cout << "pushtag " << u << " " << x << "\n";
	uadd(tag[u], x);
	dat[u].pushtag(x);
}

void upd(string l, string r, int x){
	int pl = 1, pr = 1;
	int vl = 0, vr = 0;
	vi pth;
	auto getnewnod = [&](int i, int v){
		int ret = newnod(i);
		pushtag(ret, v);
		return ret;
	};
	for(int i = n-1; i >= 0; --i){
		//cout << i << " " << pl << " " << pr << "\n";
		pth.push_back(pl);
		if(pr != pl) pth.push_back(pr);
		int dl = (int)(l[i] - '0'), dr = (int)(r[i] - '0');
		if(!ch[0][pl]) ch[0][pl] = getnewnod(i, vl);
		if(!ch[1][pl]) ch[1][pl] = getnewnod(i, add(vl, a[i]));
		if(pl != pr){
			if(!ch[0][pr]) ch[0][pr] = getnewnod(i, vr);
			if(!ch[1][pr]) ch[1][pr] = getnewnod(i, add(vr, a[i]));
			if(dl == 0) pushtag(ch[1][pl], x);
			if(dr == 1) pushtag(ch[0][pr], x);
		}
		if(dl) uadd(vl, a[i]);
		if(dr) uadd(vr, a[i]);
		pl = ch[dl][pl], pr = ch[dr][pr];
	}
	pushtag(pl, x);
	if(pr != pl) pushtag(pr, x);
	for(int i = (int)pth.size()-1; i >= 0; --i){
		int u = pth[i];
		dat[u] = nodmrg(dat[ch[0][u]], dat[ch[1][u]]);
		dat[u].pushtag(tag[u]);
	}
}

int qry(string l, string r){
	int pl = 1, pr = 1;
	int vl = 0, vr = 0;
	vi pth;
	auto getnewnod = [&](int i, int v){
		int ret = newnod(i);
		pushtag(ret, v);
		return ret;
	};
	nod ret(0, 0, 0, 0);
	for(int i = n-1; i >= 0; --i){
		pth.push_back(pl);
		if(pr != pl) pth.push_back(pr);
		int dl = (int)(l[i] - '0'), dr = (int)(r[i] - '0');
		if(!ch[0][pl]) ch[0][pl] = getnewnod(i, vl);
		if(!ch[1][pl]) ch[1][pl] = getnewnod(i, add(vl, a[i]));
		if(pl != pr){
			if(!ch[0][pr]) ch[0][pr] = getnewnod(i, vr);
			if(!ch[1][pr]) ch[1][pr] = getnewnod(i, add(vr, a[i]));
			if(dl == 0) ret = nodmrg(dat[ch[1][pl]], ret);
			if(dr == 1) ret = nodmrg(dat[ch[0][pr]], ret);
		}
		if(dl) uadd(vl, a[i]);
		if(dr) uadd(vr, a[i]);
		pl = ch[dl][pl], pr = ch[dr][pr];
	}
	ret = nodmrg(dat[pl], ret);
	if(pr != pl) ret = nodmrg(dat[pr], ret);
	for(int i = (int)pth.size()-1; i >= 0; --i){
		int u = pth[i];
		dat[u] = nodmrg(dat[ch[0][u]], dat[ch[1][u]]);
		dat[u].pushtag(tag[u]);
	}
	return ret.s[3];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	initfact(100000);

	cin >> n >> q;
	rep(i, n) cin >> a[i];
	rep(i, n) getval(i);

	newnod(n);
	//cout << dat[1].s[3] << "\n";

	while(q--){
		int tp;
		cin >> tp;
		if(tp == 1){
			string l, r; int x;
			cin >> l >> r >> x;
			upd(l, r, x);
		} else {
			string l, r;
			cin >> l >> r;
			cout << qry(l, r) << "\n";
		}
	}

	//rep(i, cn) cout << i << ": " << ch[0][i] << " " << ch[1][i] << "\n";

	return 0;
}