#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
const ll mod=998244353ll;
#define sz 1010100

ll ksm(ll x,int y){ll res=1;for (;y;y>>=1,x=x*x%mod) if (y&1) res=res*x%mod;return res;}
ll inv(ll x){return ksm(x,mod-2);}

ll fac[sz],_fac[sz];
void init(){_fac[0]=fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

struct hh {
    int s[4]; int n;
    hh(){s[0]=1,s[1]=s[2]=s[3]=n=0;}
    hh(ll x) {
        s[0]=1,s[1]=x,s[2]=0,s[3]=0;
        n=1;
    }
    hh operator + (const hh &a) const {
        hh res;
        rep(i,1,3) rep(j,0,i) res.s[i]=(res.s[i]+1ll*s[j]*a.s[i-j])%mod;
        res.n=n+a.n;
        return res;
    }
    hh operator + (const ll &x) const {
        hh res;
        res.n=n;
        rep(i,1,3) {
            ll t=1;
            drep(j,i,0) {
                res.s[i]=(res.s[i]+(ll)s[j]*t%mod*C(n-j,n-i))%mod;
                t=t*x%mod;
            }
        }
        return res;
    }
    void print() {
        cout<<n<<": ";
        rep(i,0,3) cout<<s[i]<<" \n"[i==3];
    }
};

using i128 = __int128;
const int M = 50005 * 110 * 4;

int ls[M], rs[M], add[M], cc;
hh v[M];

int cpy(int x) {
	ls[++cc] = ls[x];
	rs[cc] = rs[x];
	add[cc] = add[x];
	v[cc] = v[x];
	return cc;
}
void update(int x) {
	v[x] = (v[ls[x]] + v[rs[x]]) + add[x];
}
void put(int x, int w) {
	v[x] = v[x] + w;
	add[x] = (add[x] + w) % mod;
}
int n, q;
ll a[100];

int root;

i128 get() {
	std::string s;
	cin >> s;
	i128 res = 0;
	for(char c : s) res = res * 2 + (c - '0');
	return res;
}
i128 sgtr;
namespace {
int apply(int rt, i128 ql, i128 qr, int v, i128 l = 0, i128 r = sgtr) {
	if(ql <= l && r <= qr) {
		int x = cpy(rt); put(x, v);
		return x;
	}
	i128 mid = (l + r) >> 1;
	int x = cpy(rt);
	if(ql <= mid) ls[x] = apply(ls[rt], ql, qr, v, l, mid);
	if(mid < qr) rs[x] = apply(rs[rt], ql, qr, v, mid + 1, r);
	update(x);
	return x;
}
hh sum;
void dfs(int rt, i128 ql, i128 qr, ll tag, i128 l = 0, i128 r = sgtr) {
	if(ql <= l && r <= qr) {
		sum = sum + (v[rt] + (tag % mod));
		return ;
	}
	i128 mid = (l + r) >> 1;
	if(ql <= mid) dfs(ls[rt], ql, qr, tag + add[rt], l, mid);
	if(mid < qr) dfs(rs[rt], ql, qr, tag + add[rt], mid + 1, r);
}
}
int main() {
    file();
    init();
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> q;

	root = cc = 1;
	v[root] = hh(0);
	for(int i = 0;i < n;++i) {
		cin >> a[i];
		int R = cpy(root);
		put(R, a[i]);
		ls[++cc] = root;
		rs[cc] = R;
		update(root = cc);
	}
	sgtr = ((i128)1 << n) - 1;
	for(int i = 0;i < q;++i) {
		int op, x; i128 l, r;
		cin >> op;
		if(op == 1) {
			l = get();
			r = get();
			cin >> x;
			root = apply(root, l, r, x % mod);
		} else {
			l = get();
			r = get();
			sum = hh();
			dfs(root, l, r, 0);
			cout << sum.s[3] << '\n';
		}
	}
}