#include<bits/stdc++.h>
using namespace std;

#define int long long

using ll=__int128;

const int P=998244353,iv2=(P+1)/2,iv6=(P+1)/6,N=102,Q=5e4+7;

int n,q;

struct Data {
    int f[4];
    int d;
};

Data operator +(const Data &a,const int &b)
{
    Data ret;
    ret.d=a.d;
    ret.f[0]=1;
    ret.f[1]=(a.f[1]+a.d*b)%P;
    ret.f[2]=(a.f[2]+a.f[1]*b%P*(ret.d-1)+1ll*b*b%P*ret.d%P*(ret.d-1)%P*iv2)%P;
    ret.f[3]=(a.f[3]+a.f[2]*b%P*(ret.d-2)+1ll*b*b%P*a.f[1]%P*(ret.d-1)%P*(ret.d-2)%P*iv2+1ll*b*b%P*b%P*ret.d%P*(ret.d-1)%P*(ret.d-2)%P*iv6)%P;
    return ret;
}

Data operator +(const Data &a,const Data &b)
{
    Data ret;
    ret.d=(a.d+b.d)%P;
    for(int i=0;i<4;i++)
    {
        ret.f[i]=0;
        for(int j=0;j<=i;j++)
            ret.f[i]=(ret.f[i]+a.f[j]*b.f[i-j]);
        ret.f[i]%=P;
    }
    return ret;
}

struct T{
    signed ls,rs;
    signed tag;
    Data v;
}t[Q*N*4-2000000];

int a[N];

void update(int x,int s)
{
    t[x].v=(t[t[x].ls].v+(t[t[x].rs].v+a[s+1]));
}

Data pre[N];

int tot;

void add(int x,int v)
{
    t[x].tag=(t[x].tag+v)%P;
    t[x].v=(t[x].v+v);
}

void build(signed &x,int s)
{
    if(x)
        return;
    x=++tot;
    t[x].v=pre[s];
}

void pushdown(int x)
{
    add(t[x].ls,t[x].tag);
    add(t[x].rs,t[x].tag);
    t[x].tag=0;
}

void add(int x,int s,ll l,ll r,ll L,ll R,int v)
{
    if(L<=l&&r<=R)
    {
        add(x,v);
        return;
    }
    build(t[x].ls,s);
    build(t[x].rs,s);
    pushdown(x);
    ll mid=(l+r)/2;
    if(L<=mid)
        add(t[x].ls,s-1,l,mid,L,R,v);
    if(R>mid)
        add(t[x].rs,s-1,mid+1,r,L,R,v);
    update(x,s);
}

Data qry(int x,int s,ll l,ll r,ll L,ll R)
{
    if(L<=l&&r<=R)
        return t[x].v;
    build(t[x].ls,s);
    build(t[x].rs,s);
    pushdown(x);
    ll mid=(l+r)/2;
    if(R<=mid)
        return qry(t[x].ls,s-1,l,mid,L,R);
    else if(L>mid)
        return qry(t[x].rs,s-1,mid+1,r,L,R)+a[s];
    else
        return qry(t[x].ls,s-1,l,mid,L,R)+(qry(t[x].rs,s-1,mid+1,r,L,R)+a[s]);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    pre[0].f[0]=1;
    pre[0].d=1;
    for(int i=1;i<=n;i++)
        pre[i]=(pre[i-1]+(pre[i-1]+a[i]));
    int rt=0;
    rt=tot=1;
    t[rt].v=pre[n];
    ll S=0,T=0;
    T=1;
    for(int i=1;i<=n;i++)
        T=T*2;
    T--;
    while(q--)
    {
        int op;
        cin>>op;
        ll A=0,B=0;
        string L,R;
        cin>>L>>R;
        for(int i=0;i<n;i++)
            A=A*2+L[i]-'0';
        for(int i=0;i<n;i++)
            B=B*2+R[i]-'0';
        if(op==1)
        {
            int v;
            cin>>v;
            add(rt,n-1,S,T,A,B,v);
        }
        else
        {
            auto F=qry(1,n-1,S,T,A,B);
            auto res=F.f[3];
            cout<<res<<"\n";
        }
    }   
}