#pragma GCC Optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
long long a[105];
int cnt;
const long long mod=998244353;
#define li __int128_t
struct nod{
    int ls,rs;
    long long s1,s2,s3;
    int lz,sz;
    void add(long long val){
        lz=(lz+val)%mod;
        //(x+v)^3=x^3+3v^2x+3x^2v+v^3
        s3+=val*val%mod*s1*3+val*s2*3+val*val%mod*val%mod*sz;
        //(x+v)^2=x^2+2vx+v^2
        s2+=val*2*s1%mod+val*val%mod*sz;
        s1+=val*sz;
        s1%=mod,s2%=mod,s3%=mod;
    }
}tree[25000005];
nod merge(int id1,int id2){
    nod ans;
    ans.ls=id1,ans.rs=id2,ans.lz=0;
    ans.s1=(tree[id1].s1+tree[id2].s1)%mod;
    ans.s2=(tree[id1].s2+tree[id2].s2)%mod;
    ans.s3=(tree[id1].s3+tree[id2].s3)%mod;
    ans.sz=(tree[id1].sz+tree[id2].sz)%mod;
    return ans;
}
void pushdown(int node){
    if(tree[node].lz) {
        cnt++;
        tree[cnt] = tree[tree[node].ls], tree[cnt].add(tree[node].lz);
        cnt++;
        tree[cnt] = tree[tree[node].rs], tree[cnt].add(tree[node].lz);
        tree[node].lz = 0;
        tree[node]=merge(cnt-1,cnt);
    }
}
int update(int node,li l,li r,li L,li R,int v){
    assert(cnt<=25000000);
    ++cnt,tree[cnt]=tree[node],node=cnt;
    if(l>=L&&r<=R){
//        cout<<"#####"<<l<<" "<<r<<" "<<tree[node].s1<<" "<<tree[node].s2<<" "<<tree[node].s3<<'\n';
        tree[node].add(v);
//        cout<<"#####"<<l<<" "<<r<<" "<<tree[node].s1<<" "<<tree[node].s2<<" "<<tree[node].s3<<'\n';
        return node;
    }
//    cout<<"#####"<<l<<" "<<r<<" "<<tree[node].s1<<" "<<tree[node].s2<<" "<<tree[node].s3<<'\n';
//    cout<<"#####"<<l<<" "<<r<<" "<<tree[tree[node].ls].s1<<" "<<tree[tree[node].ls].s2<<" "<<tree[tree[node].ls].s3<<'\n';
//    cout<<"#####"<<l<<" "<<r<<" "<<tree[tree[node].rs].s1<<" "<<tree[tree[node].rs].s2<<" "<<tree[tree[node].rs].s3<<'\n';
    pushdown(node);
    li m1=(l+r)/2,m2=m1+1;
    if(m1>=L) tree[node].ls=update(tree[node].ls,l,m1,L,R,v);
    if(m2<=R) tree[node].rs=update(tree[node].rs,m2,r,L,R,v);
    tree[node]=merge(tree[node].ls,tree[node].rs);
    return node;
//    cout<<"#####"<<l<<" "<<r<<" "<<tree[node].s1<<" "<<tree[node].s2<<" "<<tree[node].s3<<'\n';
//    cout<<"#####"<<l<<" "<<r<<" "<<tree[tree[node].ls].s1<<" "<<tree[tree[node].ls].s2<<" "<<tree[tree[node].ls].s3<<'\n';
//    cout<<"#####"<<l<<" "<<r<<" "<<tree[tree[node].rs].s1<<" "<<tree[tree[node].rs].s2<<" "<<tree[tree[node].rs].s3<<'\n';
}
nod query(int node,li l,li r,li L,li R){
    if(l>=L&&r<=R) return tree[node];
    pushdown(node);
    li m1=(l+r)/2,m2=m1+1;
    if(m1<L) return query(tree[node].rs,m2,r,L,R);
    else if(m2>R) return query(tree[node].ls,l,m1,L,R);
    else{
        nod temp1=query(tree[node].ls,l,m1,L,R);
        nod temp2=query(tree[node].rs,m2,r,L,R);
        nod ans=nod{0,0,(temp1.s1+temp2.s1)%mod,(temp1.s2+temp2.s2)%mod,(temp1.s3+temp2.s3)%mod,0};
        return ans;
    }
}
long long qpow(long long a,long long b){
    long long ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--){
        int n,q;
        cin>>n>>q;
        cnt=1,tree[cnt].sz=1;
        for(int i=0;i<n;i++) {
            cin >> a[i];
            cnt++;
            tree[cnt] = tree[cnt - 1];
            tree[cnt].add(a[i]);
//            cout<<i<<" "<<cnt<<" "<<tree[cnt].s1<<" "<<tree[cnt].s2<<" "<<tree[cnt].s3<<" "<<tree[cnt].lz<<'\n';
            cnt++;
            tree[cnt] = merge(cnt - 2, cnt - 1);
//            cout<<i<<" "<<cnt<<" "<<tree[cnt].s1<<" "<<tree[cnt].s2<<" "<<tree[cnt].s3<<" "<<tree[cnt].lz<<'\n';
        }
//        for(int i=1;i<=cnt;i++) cout<<i<<" "<<tree[i].s1<<" "<<tree[i].s2<<" "<<tree[i].s3<<" "<<tree[i].lz<<'\n';
        int rt=cnt;
//        cout<<tree[rt].s1<<" "<<tree[rt].s2<<" "<<tree[rt].s3<<'\n';
        li mn=0,mx=0,now=1;
        for(int i=0;i<n;i++) mx+=now,now*=2;
        for(int i=1,t,x;i<=q;i++){
            cin>>t;
            string l,r;
            cin>>l>>r;
            li L=0,R=0,now=1;
            for(int j=0;j<n;j++) L+=(l[j]-'0')*now,R+=(r[j]-'0')*now,now*=2;
            if(t==1){
                cin>>x;
                rt=update(rt,mn,mx,L,R,x);
            }
            else{
                auto temp=query(rt,mn,mx,L,R);
//                cout<<temp.s1<<" "<<temp.s2<<" "<<temp.s3<<'\n';
                long long ans=(temp.s1*temp.s1%mod*temp.s1%mod-3*temp.s1%mod*temp.s2%mod+2*temp.s3%mod)%mod;
                ans=(ans%mod+mod)%mod;
                cout<<ans*qpow(6,mod-2)%mod<<'\n';
            }
        }
    }
    return 0;
}
//0 1 3 4 5 6 6 7