#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=5e5+10,mod=998244353; int n,q,p[maxn]; struct node{ int op,x,y,p; }d[maxn]; int dp[4005][4005],f[4005][4005]; int s[4005]; int &F(int x,int y,int p){return p?f[x][y]:f[y][x];} int &DP(int x,int y,int p){return p?dp[x][y]:dp[y][x];} int sum[maxn],sm[maxn]; void upd(int x,int y,int p){ int v=F(x,y,p); if(!p)swap(x,y); sm[x]=(sm[x]+mod-dp[x][y])%mod; sm[x]=(sm[x]+v)%mod; dp[x][y]=v; } void slv(){ n=read(),q=read(); up(i,1,n)p[i]=read(); up(i,1,q){ d[i].op=read(),d[i].x=read(); if(d[i].op>=3)d[i].y=read(); if(d[i].op!=4)d[i].p=read(); } vector<int>ve={0,n}; up(i,1,q){ if(d[i].op!=4){ ve.eb(d[i].x),ve.eb(d[i].x-1); if(d[i].op==3)ve.eb(d[i].y),ve.eb(d[i].y-1); }else ve.eb(d[i].x-1),ve.eb(d[i].y); } sort(ve.begin(),ve.end()); ve.erase(unique(ve.begin(),ve.end()),ve.end()); up(i,1,ve.size()-1)sort(p+ve[i-1]+1,p+ve[i]+1); up(i,1,ve.size()-1){ up(j,1,ve.size()-1)if(i!=j){ if(ve[i]-ve[i-1]==1){ dp[i][j]=lower_bound(p+ve[j-1]+1,p+ve[j]+1,p[ve[i]])-p-ve[j-1]-1; }else if(ve[j]-ve[j-1]==1){ dp[i][j]=ve[i]+1-(lower_bound(p+ve[i-1]+1,p+ve[i]+1,p[ve[j]])-p); } sm[i]=(sm[i]+dp[i][j])%mod; } } up(i,1,ve.size()-1)if(ve[i]!=ve[i-1]+1)up(j,ve[i-1]+1,ve[i])++sum[p[j]]; up(i,1,n)sum[i]+=sum[i-1]; up(i,1,ve.size()-1)if(ve[i]!=ve[i-1]+1){ ll ss=0;up(j,ve[i-1]+1,ve[i])ss+=sum[p[j]-1]; s[i]=(s[i-1]+ss)%mod; }else s[i]=s[i-1]; n=ve.size()-1; // cout<<"n = "<<n<<endl; up(i,1,q){ if(d[i].op==1){ int x=lower_bound(ve.begin(),ve.end(),d[i].x)-ve.begin(); up(j,1,n)up(p,0,1)F(j,x,p)=0; up(j,1,n)if(j!=x)up(p,0,1) F(j,x,p)=(F(j,x,p)+DP(j,x,p)*1llu*(mod+1-d[i].p))%mod, F(j,x,1)=(F(j,x,1)+DP(j,x,p)*1llu*d[i].p)%mod; up(j,1,n)if(j!=x)up(p,0,1)upd(j,x,p); }else if(d[i].op==2){ int x=lower_bound(ve.begin(),ve.end(),d[i].x)-ve.begin(); up(j,1,n)up(p,0,1)F(j,x,p)=0; up(j,1,n)if(j!=x)up(p,0,1) F(j,x,p)=(F(j,x,p)+DP(j,x,p)*1llu*(mod+1-d[i].p))%mod, F(j,x,0)=(F(j,x,0)+DP(j,x,p)*1llu*d[i].p)%mod; up(j,1,n)if(j!=x)up(p,0,1)upd(j,x,p); }else if(d[i].op==3){ int x=lower_bound(ve.begin(),ve.end(),d[i].x)-ve.begin(); int y=lower_bound(ve.begin(),ve.end(),d[i].y)-ve.begin(); if(x>y)swap(x,y); up(j,1,n)up(p,0,1)F(j,x,p)=F(j,y,p)=0; up(j,1,n)if(j!=x&&j!=y)up(p,0,1){ F(j,x,p)=(F(j,x,p)+DP(j,x,p)*1llu*(mod+1-d[i].p))%mod; F(j,y,p)=(F(j,y,p)+DP(j,y,p)*1llu*(mod+1-d[i].p))%mod; F(j,x,p)=(F(j,x,p)+DP(j,y,p)*1llu*d[i].p)%mod; F(j,y,p)=(F(j,y,p)+DP(j,x,p)*1llu*d[i].p)%mod; } up(p,0,1) F(y,x,p)=(F(y,x,p)+DP(x,y,p)*1llu*d[i].p)%mod, F(x,y,p)=(F(x,y,p)+DP(x,y,p)*1llu*(mod+1-d[i].p))%mod; up(j,1,n)up(p,0,1)upd(j,x,p),upd(j,y,p); }else{ int l=lower_bound(ve.begin(),ve.end(),d[i].x)-ve.begin(); int r=lower_bound(ve.begin(),ve.end(),d[i].y)-ve.begin(); int res=(s[r]-s[l-1]+mod)%mod; up(i,l,r)res=(res+sm[i])%mod; // cout<<"res = "<<res<<endl; res=(res+(d[i].y-d[i].x+1))%mod; printf("%d\n",res); } } } int main(){ //freopen("soulist.in","r",stdin),freopen("soulist.out","w",stdout); slv(); return 0; }