#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, inv6 = 166374059;
int qmod(int x){
	return x + (x >> 31 & mod);
}
void add(int &x, int y){
	x = qmod(x + y - mod);
}
struct Unit{
	int a[4];
	Unit(){
		memset(a, 0, sizeof(a));
	}
	Unit(int x){
		a[0] = 1;
		for(int i = 1; i < 4; i++)
			a[i] = 1ll * a[i - 1] * x % mod;
	}
	Unit& operator += (Unit b){
		for(int i = 0; i < 4; i++)
			add(a[i], b.a[i]);
		return *this;
	}
	Unit& operator *= (int x){
		for(int i = 3; i > 0; i--)
			for(int j = i - 1, t1 = i, t2 = x; j >= 0; t1 = t1 * j / (i - j + 1), t2 = 1ll * x * t2 % mod, j--)
				add(a[i], 1ll * t1 * t2 * a[j] % mod);
		return *this;
	}
	int val()const{
		// return a[3];
		int res = 1ll * a[1] * a[1] % mod * a[1] % mod;
		add(res, qmod(a[3] + a[3] - mod));
		res = qmod(res - 3ll * a[1] * a[2] % mod);
		return 1ll * res * inv6 % mod;
	}
};
int n, q, a[105];
#define mid (l + ((__int128)1 << d - 1))
#define r   (l + ((__int128)1 << d) - 1)
struct Seg{
	Unit s;
	int m;
	Seg *ch[2];
	Seg():s(){
		m = 0;
		ch[0] = ch[1] = 0;
	}
	Seg(Seg *x){
		if(x){
			m = x->m;
			ch[0] = x->ch[0];
			ch[1] = x->ch[1];			
		}
	}
	Seg *get(int k, Seg *pre = 0){
		return ch[k] = new Seg(pre);
	}
	void pushup(int d){
		if(!d) return s = m, void();
		s = ch[0] ? ch[0]->s : Unit();
		if(ch[1]) s += ch[1]->s;
		if(m) s *= m;
	}
	void build(int d = n, __int128 l = 0){
		if(!d) return s = m, void();
		get(0)->build(d - 1, l);
		get(1, ch[0]); ch[1]->m = a[d - 1];
		ch[1]->pushup(d - 1);
		pushup(d);
	}
	void print(int d = n, __int128 l = 0){
		printf("%d %d %d\n", d, s.val(), m);
		if(!d) return;
		ch[0]->print(d - 1, l);
		ch[1]->print(d - 1, mid);
	}
	void upd(Seg *pre, __int128 L, __int128 R, int x, int d = n, __int128 l = 0){
		// cout << d << " " << (int)l << endl;
		if(L <= l && R >= r){
			add(m, x);
			pushup(d);
			return;
		}
		if(L < mid) get(0, pre->ch[0])->upd(pre->ch[0], L, R, x, d - 1, l);
		if(R >= mid) get(1, pre->ch[1])->upd(pre->ch[1], L, R, x, d - 1, mid);
		pushup(d);
	}
	Unit query(__int128 L, __int128 R, int lazy = 0, int d = n, __int128 l = 0){
		if(L <= l && R >= r){
			Unit res = s;
			return res *= lazy;
		}
		add(lazy, m);
		Unit res = L < mid ? ch[0]->query(L, R, lazy, d - 1, l) : Unit();
		if(R >= mid) res += ch[1]->query(L, R, lazy, d - 1, mid);
		return res;
	}
}*rt[50004];
#undef r
__int128 btoi(string &s){
	__int128 res = 0;
	for(int i = 0; i < n; i++)
		res = res << 1 | s[i] ^ '0';
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i] = qmod(a[i] - mod);
	}
	(rt[0] = new Seg())->build();
	// rt[0]->print();
	for(int i = 1, op; i <= q; i++){
		rt[i] = new Seg();
		string s1, s2;
		cin >> op >> s1 >> s2;
		__int128 l = 0, r = 0;
		l = btoi(s1); r = btoi(s2);
		if(op == 1){
			int x;
			cin >> x;
			rt[i]->upd(rt[i - 1], l, r, qmod(x - mod));
			// rt[i]->print();
		}
		else{
			rt[i] = rt[i - 1];
			printf("%d\n", rt[i]->query(l, r).val());
			// rt[i]->print();
		}
	}
	return 0;
}