#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 #define ppc __builtin_popcount 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; } int n,q,w[5005],cnt[5005]; const int p=998244353; inline int add(int a,int b){if((a+=b)>=p)a-=p;return a;} namespace Poly{ const int n=13; const int G=3,Gi=332748118; inline int qp(int a,int b){ int res=1; for(;b;b>>=1,a=a*1llu*a%p)if(b&1)res=res*1llu*a%p; return res; } int rev[1<<n],mul[2][1<<n]; void init(){ up(i,1,(1<<n)-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<n-1); up(op,0,1)for(int k=1;k<(1<<n);k<<=1){ int v=qp(op?Gi:G,(p-1)/k/2); mul[op][k]=1;up(j,1,k-1)mul[op][j+k]=mul[op][j+k-1]*1llu*v%p; } } void ntt(int *a,int op){ up(i,0,(1<<n)-1)if(i<rev[i])swap(a[i],a[rev[i]]); for(int k=1;k<(1<<n);k<<=1){ for(int i=0;i<(1<<n);i+=k<<1) up(j,i,i+k-1){ int x=a[j],y=a[j+k]*1llu*mul[op][k+j-i]%p; a[j]=add(x,y),a[j+k]=add(x,p-y); } } if(op){int iv=qp(1<<n,p-2);up(i,0,(1<<n)-1)a[i]=a[i]*1llu*iv%p;} } } const int N=8192; int sm[10005][N],va[N]; inline int ind(int l,int r){return l+r|l!=r;} void pu(int l,int r){ int mid=l+r>>1,p=ind(l,r),ls=ind(l,mid),rs=ind(mid+1,r); up(i,0,N-1)sm[p][i]=sm[ls][i]*1llu*sm[rs][i]%(::p); } void bd(int l,int r){ if(l==r){int p=ind(l,r);up(i,0,N-1)sm[p][i]=1;return;} int mid=l+r>>1;bd(l,mid),bd(mid+1,r);pu(l,r); } void upd(int l,int s,int t){ if(s==t){int p=ind(s,t);up(i,0,N-1)sm[p][i]=va[i];return;} int mid=s+t>>1;if(l<=mid)upd(l,s,mid);else upd(l,mid+1,t);pu(s,t); } void qr(int l,int r,int s,int t){ if(l<=s&&t<=r){int p=ind(s,t);up(i,0,N-1)va[i]=va[i]*1llu*sm[p][i]%(::p);return;} int mid=s+t>>1;if(l<=mid)qr(l,r,s,mid);if(r>mid)qr(l,r,mid+1,t); } void slv(){ n=read(),q=read();up(i,1,n)w[i]=read(); Poly::init();bd(1,n); while(q--){ int op=read(); if(op<=2){ int x=read(),v=read(); if(op&1)cnt[x]+=v;else cnt[x]-=v; up(i,0,N-1)va[i]=0; if(cnt[x]){up(i,0,cnt[x])va[w[x]*i]=1;Poly::ntt(va,0);} else up(i,0,N-1)va[i]=1;upd(x,1,n); }else{ int l=read(),r=read(),k=read(); up(i,0,N-1)va[i]=1;qr(l,r,1,n);Poly::ntt(va,1); int res=p-1;up(i,0,k)res=add(res,va[i]); printf("%d\n",res); } } } int main(){ // freopen("biden.in","r",stdin),freopen("biden.out","w",stdout); slv(); return 0; }