记录编号	443262	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2017]蚯蚓排队	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	6.994 s
提交时间	2017-08-30 09:45:48	内存使用	931.08 MiB

//pretest passed
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
int read(){
	int x=0;bool sign=0;
	char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return sign?-x:x;
}
typedef long long ll;
const int N=5e5+10,p=119<<23|1;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int n,m,maxk,c[N],nxt[N],pre[N];
const int nodes=3e7+10;
int go[nodes][6],cnt[nodes],fail[nodes],top=1;
int extend(int p,int w){
	if (!go[p][w]) fail[go[p][w]=++top]=go[fail[p]][w];
	return go[p][w];
}
int tp,x,y,k;
const int length=1e7+10;
char s[length];
int main()
{
	freopen("2017queue.in","r",stdin);
	freopen("2017queue.out","w",stdout);
	scanf("%d%d",&n,&m);
	if (m<=300000) maxk=50;else maxk=1;
	for (int i=0;i<6;i++) fail[go[1][i]=++top]=1;
	for (int i=1;i<=n;i++) c[i]=read(),++cnt[go[1][c[i]-1]];
	for (int i=1;i<=m;i++){
		tp=read();
		if (tp==1){
			x=read();y=read();
			nxt[x]=y;pre[y]=x;
			for (int i=1;i<maxk&&x;i++,x=pre[x]){
				int p=1,now=x;
				for (int j=1;j<=i;j++){
					int w=c[now]-1;
					p=extend(p,w);
					now=nxt[now];
				}
				for (int j=i+1;now&&j<=maxk;j++){
					int w=c[now]-1;
					p=extend(p,w);
					cnt[p]++;
					now=nxt[now];
				}
			}
		}
		if (tp==2){
			x=read();y=nxt[x];
			for (int i=1;i<maxk&&x;i++,x=pre[x]){
				int p=1,now=x;
				for (int j=1;j<=i;j++){
					int w=c[now]-1;
					p=extend(p,w);
					now=nxt[now];
				}
				for (int j=i+1;now&&j<=maxk;j++){
					int w=c[now]-1;
					p=extend(p,w);
					cnt[p]--;
					now=nxt[now];
				}
			}
			nxt[pre[y]]=0;pre[y]=0;
		}
		if (tp==3){
			scanf("%s",s+1);
			k=read();
			n=strlen(s+1);s[n+1]=1;
			int ans=1,p=1;
			for (int i=1;i<=k;i++) p=go[p][s[i]-'1'];
			for (int i=k+1;i<=n+1;i++) ans=mul(ans,cnt[p]),p=go[fail[p]][s[i]-'1'];
			printf("%d\n",ans);
		}
	}
	return 0;
}