#include<cstdio>
#define re register
#define ull unsigned long long
using namespace std;
const int Mxdt=1000000; //单次大小
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool bj){
static char buf[Mxdt],*p1=buf,*p2=buf+Mxdt;
return (bj||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
void print(int x)
{
if(x>9)print(x/10);
pc(x%10^48,false);
}
inline void printnum(int x,char ch)
{
print(x),pc(ch,false);
}
inline int read(){
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;
struct hashtable{
int head[65536];
inline void ins(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;
}
inline int ask(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];
return 0;
}
}H[52];
int n,L[500002],R[500002],m,l,a[500002],k;
char s[10000002];
const int M=998244353;
int main(){
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');
}
else if(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);
}