#include<cstdio>#define re register#define ull unsigned long longusingnamespacestd;
constint Mxdt=1000000; //单次大小 inlinechargc(){
staticchar buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inlinecharpc(char ch,bool bj){
staticchar buf[Mxdt],*p1=buf,*p2=buf+Mxdt;
return (bj||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
voidprint(int x){
if(x>9)print(x/10);
pc(x%10^48,false);
}
inlinevoidprintnum(int x,char ch){
print(x),pc(ch,false);
}
inlineintread(){
re int t=0;re char v=gc();
while(v<'0')v=gc();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
return t;
}
int nxt[20000002],cnt,val[20000002];
ull to[20000002],pw[52],B=131;
structhashtable{int head[65536];
inlinevoidins(re ull x,re int y){
re int tmp=x&65535;
for(re int i=head[tmp];i;i=nxt[i])if(to[i]==x){val[i]+=y;return;}
to[++cnt]=x,nxt[cnt]=head[tmp],head[tmp]=cnt,val[cnt]=y;
}
inlineintask(re ull x){
re int tmp=x&65535;
for(re int i=head[tmp];i;i=nxt[i])if(to[i]==x)return val[i];
return0;
}
}H[52];
int n,L[500002],R[500002],m,l,a[500002],k;
char s[10000002];
constint M=998244353;
intmain(){
n=read(),m=read();
for(re int i=pw[0]=1;i<=n;++i)pw[i]=pw[i-1]*B;
for(re int i=1;i<=n;++i)a[i]=read(),H[1].ins(a[i],1);
while(m--){
re int o=read();
if(o==3){
l=0;
while(s[l]^' ')s[++l]=gc();
k=read(),--l;
re ull hsh=0;
for(re int i=1;i<=k;++i)hsh=hsh*B+s[i]-'0';
re int ans=H[k].ask(hsh);
for(re int i=k+1;i<=l;++i)hsh=hsh*B+s[i]-'0',hsh-=pw[k]*(s[i-k]-'0'),ans=1ll*ans*H[k].ask(hsh)%M;
printnum(ans,'\n');
}
elseif(o==2){
re int x=R[read()];
for(re int s=L[x],t=1;s&&t<=50;++t,s=L[s]){
re ull hsh=0;
for(re int y=s,c=1;c<=50&&y;++c,y=R[y]){hsh=hsh*B+a[y];if(c>t)H[c].ins(hsh,-1);}
}
R[L[x]]=0,L[x]=0;
}
else{
re int x=read(),y=read();
R[x]=y,L[y]=x;
for(re int s=x,t=1;s&&t<=50;++t,s=L[s]){
re ull hsh=0;
for(re int y=s,c=1;c<=50&&y;++c,y=R[y]){hsh=hsh*B+a[y];if(c>t)H[c].ins(hsh,1);}
}
}
}
pc('o',1);
}