#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
long long int n,m,a[N],len,id[N],tag[N],Tag[N],minn[N],cnt[N],vis[N];
long long int md=998244353;
void fix(int l,int r){
    int sid=id[l],eid=id[r];
    if(sid==eid){
        for(int i=l;i<=r;i++){
            if(tag[i]+Tag[sid]>0){
                tag[i]--;
                minn[sid]=min(minn[sid],tag[i]+Tag[sid]);
            }
            else{
                a[i]=sqrt(a[i]);
                if(a[i]==1&&vis[i]==0){
                    cnt[sid]++;
                    vis[i]=1;
                }
            }
        }
        return;
    }
    for(int i=l;id[i]==sid;i++){
        if(tag[i]+Tag[sid]>0){
            tag[i]--;
            minn[sid]=min(minn[sid],tag[i]+Tag[sid]);
        }
        else{
            a[i]=sqrt(a[i]);
            if(a[i]==1&&vis[i]==0){
                cnt[sid]++;
                vis[i]=1;
            }
        }
    }
    for(int i=sid+1;i<eid;i++){
        if(cnt[i]!=len){
            if(minn[i]>0){
                Tag[i]--;
                minn[i]--;
            }
            else if(minn[i]==0){
                for(int j=(i-1)*len+1;id[j]==i;j++){
                    if(tag[j]+Tag[i]>0){
                        tag[j]--;
                    }
                    else{
                        a[j]=sqrt(a[j]);
                        if(a[j]==1&&vis[j]==0){
                            cnt[i]++;
                            vis[j]=1;
                        }
                    }
                }
            }
        }
    }
    for(int i=r;id[i]==eid;i--){
        if(tag[i]+Tag[eid]>0){
            tag[i]--;
            minn[eid]=min(minn[eid],tag[i]+Tag[eid]);
        }
        else{
            a[i]=sqrt(a[i]);
            if(a[i]==1&&vis[i]==0){
                cnt[eid]++;
                vis[i]=1;
            }
        }
    }
    return;
}
void fix_2(int l,int r){
    int sid=id[l],eid=id[r];
    if(sid==eid){
        for(int i=l;i<=r;i++){
            tag[i]++;
        }
        minn[sid]=1e18;
        for(int i=(sid-1)*len+1;id[i]==sid;i++){
            minn[sid]=min(minn[sid],tag[i]+Tag[sid]);
        }
        return;
    }
    for(int i=l;id[i]==sid;i++){
        tag[i]++;
    }
    minn[sid]=1e18;
    for(int i=(sid-1)*len+1;id[i]==sid;i++){
        minn[sid]=min(minn[sid],tag[i]+Tag[sid]);
    }
    for(int i=sid+1;i<eid;i++){
        if(cnt[i]!=len){
            Tag[i]++;
            minn[i]++;
        }
    }
    for(int i=r;id[i]==eid;i--){
        tag[i]++;
    }
    minn[eid]=1e18;
    for(int i=(eid-1)*len+1;id[i]==eid;i++){
        minn[eid]=min(minn[eid],tag[i]+Tag[eid]);
    }
    return;
}
int main(){
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/len+1;
    }
    for(int i=1;i<=m;i++){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            fix(l,r);
        }
        if(op==2){
            fix_2(l,r);
        }
    }
    long long int ans=0;
    for(int i=1;i<=n;i++){
        long long int y=pow(2,(tag[i]+Tag[id[i]]));
        y=y%(md-1);
        long long int x=pow(a[i],y);
        x=x%md;
        ans+=x;
    }
    cout<<ans;
    return 0;
}