#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

typedef __int128 Int;

// snuke's mod int
template <ll mod>
struct modint{
	ll x;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

using mint=modint<998244353>;

typedef vec(mint) vm;

struct F{
	mint len=0;
	vm dp={0,0,0};
	F operator+(const F&a)const{
		F res;
		rep(j,3) res.dp[j]+=a.dp[j];
		return res;
	}
	void add(mint x){
		dp[2]=dp[2]+dp[1]*(len-2)*x*mint(3)+dp[0]*(len-1)*(len-2)*x*x*mint(3)+x*x*x*len*(len-1)*(len-2);
		dp[1]=dp[1]+dp[0]*(len-1)*x*mint(2)+x*x*len*(len-1);
		dp[0]=dp[0]+x*len;
	}
};

F merge(F l,F r){
	F res;
	res.len=l.len+r.len;
	res.dp[0]=l.dp[0]+r.dp[0];
	res.dp[1]+=l.dp[1];
	res.dp[1]+=r.dp[1];
	res.dp[1]+=(l.dp[0]*r.dp[0])*mint(2);
	res.dp[2]+=l.dp[2];
	res.dp[2]+=r.dp[2];
	res.dp[2]+=l.dp[0]*r.dp[1]*mint(3);
	res.dp[2]+=l.dp[1]*r.dp[0]*mint(3);
	return res;
}

void print(Int n){
	if(n==0) return;
	print(n/10);
	cout<<(int)(n%10);
}

int n,q;

vi a;

vec(F) ps;

Int pot[210];

int ptr=0;

struct N{
	int sart=0;
	int lc=-1,rc=-1;
	int tag=0;
	mint ad=0;
	F res;
}seg[5000000];

void apply(int node){
	if(seg[node].sart!=n and seg[node].lc==-1){
		seg[node].lc=++ptr;
		seg[ptr].sart=seg[node].sart+1;
		// print(seg[ptr].sart);
		if(n-seg[ptr].sart<0){
			print("wtf");
			exit(0);
		}
		seg[ptr].res=ps[n-seg[ptr].sart];
	}
	if(seg[node].sart!=n and seg[node].rc==-1){
		seg[node].rc=++ptr;
		seg[ptr].sart=seg[node].sart+1;
		// print(seg[ptr].sart);
		if(n-seg[ptr].sart<0){
			print("wtf");
			exit(0);
		}
		seg[ptr].res=ps[n-seg[ptr].sart];
	}
	if(seg[node].tag){
		mint x=seg[node].ad;
		seg[node].res.add(x);
		if(seg[node].lc!=-1){
			seg[seg[node].lc].tag=1;
			seg[seg[node].lc].ad+=x;
		}
		if(seg[node].rc!=-1){
			seg[seg[node].rc].tag=1;
			seg[seg[node].rc].ad+=x;
		}
		seg[node].tag=0;
		seg[node].ad=0;
	}
}

F prod(int node,Int l,Int r,Int s,Int e){
	apply(node);
	if(l>=e or r<=s){
		return F{};
	}
	// print(l);
	// print();
	// print(r);
	// print();
	if(s<=l and r<=e){
		// print("wtf go",node,n-seg[node].sart);
		// print(l);
		// print();
		// print(r);
		// print();
		// print((int)l,(int)r,(int)(s),(int)(e));
		return seg[node].res;
	}
	Int m=(l+r)/2;
	// print("wtf");
	// print(s);
	// print();
	// print(e);
	// print();
	// return F{};
	auto val_l=prod(seg[node].lc,l,m,s,e);
	auto val_r=prod(seg[node].rc,m,r,s,e);
	if(seg[node].sart!=n) val_r.add(a[n-1-seg[node].sart]);
	// print((int)l,(int)r,(int)(s),(int)(e));
	// print(val_r.len.x,a[n-1-seg[node].sart]);
	return merge(val_l,val_r);
	// return merge(prod(seg[node].lc,l,m,s,e),);
}

void add(int node,Int l,Int r,Int s,Int e,int x){
	apply(node);
	if(l>=e or r<=s){
		return;
	}
	if(s<=l and r<=e){
		seg[node].tag=1;
		seg[node].ad+=x;
		apply(node);
		return;
	}
	Int m=(l+r)/2;
	add(seg[node].lc,l,m,s,e,x);
	add(seg[node].rc,m,r,s,e,x);
	auto val_l=seg[seg[node].lc].res;
	auto val_r=seg[seg[node].rc].res;
	if(seg[node].sart!=n) val_r.add(a[n-1-seg[node].sart]);
	// print((int)l,(int)r,(int)(s),(int)(e));
	// print(val_r.len.x,a[n-1-seg[node].sart]);
	seg[node].res=merge(val_l,val_r);
}

Int toInt(string s){
	Int now=0;
	rep(i,sz(s)){
		now*=2;
		now+=(s[i]-'0');
	}
	return now;
}

void slv(){
	cin>>n>>q;

	a=vi(n,0);
	rep(i,n) cin>>a[i];

	F now;
	now.len=1;
	ps.pb(now);
	rep(i,n){
		now=ps.back();
		now.add(a[i]);
		// print(now.dp[2].x);
		ps.pb(merge(ps.back(),now));
	}

	pot[0]=1;
	rng(i,1,n+1) pot[i]=pot[i-1]*Int(2);

	{
		int node=0;
		seg[node].sart=0;
		seg[node].res=ps[n];
		seg[node].res.len=pot[n];
	}

	rep(i,q){
		int t;
		cin>>t;
		string l,r;
		cin>>l>>r;
		{
			bool fnd=0;
			per(j,sz(r)){
				if(r[j]=='0'){
					fnd=1;
					r[j]='1';
					break;
				}
				r[j]='0';
			}
			if(!fnd) r.insert(r.begin(),'1');
		}
		// print(r);
		if(t==1){
			int x;
			cin>>x;
			add(0,0,pot[n],toInt(l),toInt(r),x);
		}else{
			// print(toInt(l));
			// print(toInt(r));
			// print("e");
			auto res=prod(0,0,pot[n],toInt(l),toInt(r));
			mint ans=res.dp[2];
			ans*=mint(6).inv();
			print(ans.x);
		}
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	slv();
}