#include<bits/stdc++.h>
#define LL long long
#define bll __int128
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
inline int rd()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
inline bll rd1()
{
	bll x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*2+ch-'0',ch=getchar();
	return x;
}
const int N=2e7+5,mod=998244353,I6=(mod+1)/6;
int n,q,rt,a[105],tot;
inline int md(int x){return x>=mod?x-mod:x;}
struct node
{
	int s0,s1,s2,s3;
	inline node operator+(node X){return {md(s0+X.s0),md(s1+X.s1),md(s2+X.s2),md(s3+X.s3)};}
	inline node operator+(int x){return {s0,(s1+1ll*s0*x)%mod,(s2+1ll*s0*x%mod*x+2ll*s1*x)%mod,
	(s3+1ll*s0*x%mod*x%mod*x+3*(1ll*s1*x%mod*x+1ll*s2*x))%mod};}
	inline int que(){return ((2ll*s3-3ll*s1*s2+1ll*s1*s1%mod*s1)%mod+mod)*I6%mod;}
}b[105];
struct tree{int ls,rs,lt;node t;}c[N];
#define ls c[wz].ls
#define rs c[wz].rs
inline void init(bll l,bll r,int &wz)
{
	bll s=1;int t,S=0;for(int i=0;;i++,s<<=1) if(s==r-l+1){t=i;break;}
	for(int i=0;i<n;i++) if(l>>i&1) S=md(S+a[i]);c[wz=++tot].t=b[t]+S;
//	cout<<(LL)l<<" "<<(LL)r<<" "<<t<<":\n";
//	cout<<c[wz].t.s0<<" "<<c[wz].t.s1<<" "<<c[wz].t.s2<<" "<<c[wz].t.s3<<"\n";
}
inline void upd(int wz,int x){c[wz].lt+=x,c[wz].t=c[wz].t+x;}
inline void pushdown(bll l,bll r,bll mid,int wz)
{
	if(!ls) init(l,mid,ls);if(!rs) init(mid+1,r,rs);
	int t=c[wz].lt;if(t) upd(ls,t),upd(rs,t),c[wz].lt=0;
}
void updata(bll l,bll r,int &wz,bll L,bll R,int x)
{
	if(!wz) init(l,r,wz);
	if(L<=l&&r<=R) return upd(wz,x);bll mid=(l+r)>>1;pushdown(l,r,mid,wz);
	if(L<=mid) updata(l,mid,ls,L,R,x);
	if(mid<R) updata(mid+1,r,rs,L,R,x);c[wz].t=c[ls].t+c[rs].t;
}
node query(bll l,bll r,int &wz,bll L,bll R)
{
	if(!wz) return init(l,r,wz),c[wz].t;if(L<=l&&r<=R) return c[wz].t;
	bll mid=(l+r)>>1;pushdown(l,r,mid,wz);
	if(L<=mid&&mid<R) return query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R);
	if(L<=mid) return query(l,mid,ls,L,R);return query(mid+1,r,rs,L,R);
}
int cs[10];
int main()
{
	n=rd(),q=rd();for(int i=0;i<n;i++) a[i]=rd();
//	for(int i=0;i<(1<<n);i++)
//	{
//		for(int j=0;j<n;j++) if(i>>j&1) cs[i]+=a[j];
//		cout<<cs[i]<<" "; 
//	}cout<<"\n";
	b[0]={1,0,0,0};
	for(int i=1;i<=n;i++) b[i]=b[i-1]+(b[i-1]+a[i-1]);bll U=((bll)1)<<n;
//	for(int i=0;i<=n;i++) cout<<b[i].s1<<" ";cout<<"\n";
	while(q--)
	{
		int o=rd();bll l=rd1(),r=rd1();
		if(o==1) updata(0,U-1,rt,l,r,rd());
		else cout<<query(0,U-1,rt,l,r).que()<<"\n";
	}
	return 0;
}
/*
3 3
1 2 4
2 000 111
1 010 101 1
2 000 111
*/