#include<bits/stdc++.h>
#define MAXN 200010
#define INF 1000000010
#define MOD 998244353
#define LL long long
#define LLL __int128_t
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int mo(int x){return x>=MOD?x-MOD:x;}
void moplus(int &x,int y){x=mo(x+y);}
int inv2=(MOD+1)/2;
int inv6=(MOD+1)/6;
struct node{
    int v[4];
    int len;
};
node operator+(node x,node y){
    node z;
    For(i,0,3){
        z.v[i]=0;
        For(j,0,i){
            moplus(z.v[i],1LL*x.v[j]*y.v[i-j]%MOD);
        }
    }
    z.len=mo(x.len+y.len);
    return z;
}
node operator+(node x,int y){
    int miy[4];
    miy[0]=1;
    For(i,1,3) miy[i]=1LL*miy[i-1]*y%MOD;
    moplus(x.v[3],(1LL*x.v[2]*y%MOD*(x.len-2)%MOD+
                   1LL*x.v[1]*miy[2]%MOD*(1LL*(x.len-1)*(x.len-2)/2%MOD)%MOD+
                   1LL*x.len*(x.len-1)%MOD*(x.len-2)%MOD*inv6%MOD*miy[3]%MOD)%MOD);
    moplus(x.v[2],(1LL*x.v[1]*y%MOD*(x.len-1)%MOD+
                   1LL*(x.len-1)*x.len/2%MOD*miy[2]%MOD)%MOD);
    moplus(x.v[1],1LL*x.len*y%MOD);
    return x;
}
const int N=110,Q=50000,V=16000000;
node f[N];
int a[N];
struct Segtree{
    node v[V];
    int lc[V],rc[V],tag[V],vcnt=0;
    int rt=0;
    int newnode(int d,int s){
        int id=++vcnt;
        v[id]=f[d]+s;
        lc[id]=rc[id]=tag[id]=0;
        return id;
    }
    void down(int &id,int d,int s,int z){
        if (!id) id=newnode(d,s);
        v[id]=v[id]+z;
        moplus(tag[id],z);
    }
    void pushdown(int id,int d,int s){
        if (tag[id]){
            down(lc[id],d-1,s,tag[id]);
            down(rc[id],d-1,mo(s+a[d-1]),tag[id]);
            tag[id]=0;
        }
    }
    void update(int id,int d,int s){
        if (!lc[id]) lc[id]=newnode(d-1,s);
        if (!rc[id]) rc[id]=newnode(d-1,mo(s+a[d-1]));
        v[id]=v[lc[id]]+v[rc[id]];
    }
    void modify(int &id,LLL l,LLL r,int d,int s,LLL x,LLL y,int z){
        if(!id) id=newnode(d,s);
        if (l==x&&r==y){
            down(id,d,s,z);
            return ;
        }
        pushdown(id,d,s);
        LLL mid=l+r>>1;
        if (y<=mid) modify(lc[id],l,mid,d-1,s,x,y,z);
        else if (x>mid) modify(rc[id],mid+1,r,d-1,mo(s+a[d-1]),x,y,z);
        else modify(lc[id],l,mid,d-1,s,x,mid,z),modify(rc[id],mid+1,r,d-1,mo(s+a[d-1]),mid+1,y,z);
        update(id,d,s);
    }
    node query(int &id,LLL l,LLL r,int d,int s,LLL x,LLL y){
        if(!id) id=newnode(d,s);
        if (l==x&&r==y) return v[id];
        pushdown(id,d,s);
        LLL mid=l+r>>1;
        if (y<=mid) return query(lc[id],l,mid,d-1,s,x,y);
        else if (x>mid) return query(rc[id],mid+1,r,d-1,mo(s+a[d-1]),x,y);
        else return query(lc[id],l,mid,d-1,s,x,mid)+query(rc[id],mid+1,r,d-1,mo(s+a[d-1]),mid+1,y);
    }
}T;
char s[N];
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;cin>>n>>q;
    int L=0,R=(((LLL)1)<<n)-1;
    For(i,0,n-1) cin>>a[i];
    f[0].len=1;
    For(i,1,3) f[0].v[i]=0;
    f[0].v[0]=1;
    For(i,1,n) f[i]=f[i-1]+(f[i-1]+a[i-1]);
    while (q--){
        int op;LLL x=0,y=0;
        cin>>op;
        cin>>s+1;
        Rof(i,n,1) x=1LL*x*2+s[i]-'0';
        cin>>s+1;
        Rof(i,n,1) y=1LL*y*2+s[i]-'0';
        if (op==1){
            int z;cin>>z;
            z=mo(z);
            T.modify(T.rt,L,R,n,0,x,y,z);
        }else{
            cout<<T.query(T.rt,L,R,n,0,x,y).v[3]<<"\n";
        }
    }
}
/*
3 3
1 2 4
2 000 111
1 010 101 1
2 000 111

2 2
1 1
2 00 10
2 00 11
*/