#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define wln putchar('\n')
#define lll __int128_t
template<class T1,class T2> void chkmin(T1 &x,T2 y){if(y<x)x=y;}
template<class T1,class T2> void chkmax(T1 &x,T2 y){if(y>x)x=y;}
const int N=101,M=50005,V=16000000;
const int MOD=998244353;
int mo(int x){return x>=MOD?x-MOD:x;};
void moplus(int &x,int y){x=mo(x+y);}
struct node{int f1[2],f2[2][2],f3[2][2][2];}f0[N];
int a[N],n,q;
node operator +(node a,node b)
{
    node c;
    For(i,0,1)
        For(j,0,1)
            For(k,0,1)
            {
                c.f3[i][j][k]=mo(a.f3[i][j][k]+b.f3[i][j][k]);
                moplus(c.f3[i][j][k],1ll*a.f1[i]*b.f2[j][k]%MOD);
                moplus(c.f3[i][j][k],1ll*a.f2[i][j]*b.f1[k]%MOD);
            }
    For(i,0,1)
        For(j,0,1)
        {
            c.f2[i][j]=mo(a.f2[i][j]+b.f2[i][j]);
            moplus(c.f2[i][j],1ll*a.f1[i]*b.f1[j]%MOD);
        }
    For(i,0,1)c.f1[i]=mo(a.f1[i]+b.f1[i]);
    return c;
}
node operator +(node a,int x)
{
    if(x==0)return a;
    node b;
    int px[4];
    px[0]=1;
    For(i,1,3)px[i]=1ll*px[i-1]*x%MOD;
    For(i,0,1)
        For(j,0,1)
            For(k,0,1)
            {
                b.f3[i][j][k]=0;
                For(ii,0,i)
                    For(jj,0,j)
                        For(kk,0,k)
                            moplus(b.f3[i][j][k],1ll*px[i+j+k-ii-jj-kk]*a.f3[ii][jj][kk]%MOD);
            }
    For(i,0,1)
        For(j,0,1)
        {
            b.f2[i][j]=0;
            For(ii,0,i)
                For(jj,0,j)
                    moplus(b.f2[i][j],1ll*px[i+j-ii-jj]*a.f2[ii][jj]%MOD);
        }
    For(i,0,1)
    {
        b.f1[i]=0;
        For(ii,0,i)
            moplus(b.f1[i],1ll*px[i-ii]*a.f1[ii]%MOD);
    }
    return b;
}
struct segtree
{
    node v[V];
    int rt;
    int tag[V],ls[V],rs[V],vcnt;
    int newnode(int d,int s)
    {
        int id=++vcnt;
        if (vcnt>=16000000-10){
            while (1);
        }
        v[id]=f0[d]+s;
        return id;
    }
    void pushup(int id,int d,int s)
    {
        int ss=mo(s+a[d-1]);
        v[id]=(ls[id]?v[ls[id]]:f0[d-1]+s)+(rs[id]?v[rs[id]]:f0[d-1]+ss);
    }
    void down(int &id,int d,int s,int x)
    {
        if(!id)id=newnode(d,s);
        v[id]=v[id]+x; 
        moplus(tag[id],x);
    }
    void pushdown(int id,int d,int s)
    {
        if(tag[id])
        {
            int ss=mo(s+a[d-1]);
            down(ls[id],d-1,s,tag[id]);
            down(rs[id],d-1,ss,tag[id]);
            tag[id]=0;
        }
    }
    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(x<=l&&r<=y){down(id,d,s,z); return;}
        lll mid=l+r>>1;
        pushdown(id,d,s);
        int ss=mo(s+a[d-1]);
        if(x<=mid)modify(ls[id],l,mid,d-1,s,x,y,z);
        if(y>mid)modify(rs[id],mid+1,r,d-1,ss,x,y,z);
        pushup(id,d,s);
    }
    node query(int &id,lll l,lll r,int d,int s,lll x,lll y)
    {
        //static int cnt=0;
        if(!id)id=newnode(d,s);
        //printf("query:%d %d %d %d %d %d %d\n",id,l,r,s,d,x,y);
        if(x<=l&&r<=y)return v[id];
        lll mid=l+r>>1;
        pushdown(id,d,s);
        int ss=mo(s+a[d-1]);
        if(x>mid)return query(rs[id],mid+1,r,d-1,ss,x,y);
        if(y<=mid)return query(ls[id],l,mid,d-1,s,x,y);
        return query(ls[id],l,mid,d-1,s,x,y)+query(rs[id],mid+1,r,d-1,ss,x,y);
    }
}T;
int main()
{
    scanf("%d%d",&n,&q);
    For(i,0,n-1)scanf("%d",a+i),a[i]=mo(a[i]);
    lll L=0,R=((lll)1<<n)-1;
    f0[0].f1[0]=1;
    f0[0].f1[1]=0;
    For(i,1,n)f0[i]=f0[i-1]+(f0[i-1]+a[i-1]);
    while(q--)
    {
        int opt;
        char s[N];
        scanf("%d",&opt);
        lll x=0,y=0;
        scanf("%s",s);
        Rof(i,n-1,0)x=x*2+s[i]-'0';
        scanf("%s",s);
        Rof(i,n-1,0)y=y*2+s[i]-'0';
        if(opt==1)
        {
            int z;
            scanf("%d",&z); z=mo(z);
            T.modify(T.rt,L,R,n,0,x,y,z);
        }
        else printf("%d\n",T.query(T.rt,L,R,n,0,x,y).f3[1][1][1]);
    }
}
/*
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
*/