//It is made by wfj_2048~

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #define rhl (998244353)

 #define wyh (19260817)

 #define M (10000010)

 #define N (300010)

 #define il inline

 #define RG register

 #define ll long long

 #define ull unsigned long long

 using namespace std;

 struct edge{ int nt,sum; ull v; }g[];

 int head[wyh+],a[N],lst[N],nxt[N],st1[],st2[],tong[],n,m,num,fg,top1,top2;

 ull hsh[M],bin[M],base=;

 char s[M];

 ll ans;

 il int gi(){

     RG int x=,q=; RG char ch=getchar();

     while ((ch<'' || ch>'') && ch!='-') ch=getchar();

     if (ch=='-') q=-,ch=getchar();

     while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

     return q*x;

 }

 il void insert(RG int from,RG ull to){

     g[++num]=(edge){head[from],,to},head[from]=num; return;

 }

 il void add(RG ull Hash){

     RG int ymd=Hash%wyh;

     for (RG int i=head[ymd];i;i=g[i].nt)

     if (g[i].v==Hash){ ++g[i].sum; return; }

     return insert(ymd,Hash);

 }

 il void del(RG ull Hash){

     RG int ymd=Hash%wyh;

     for (RG int i=head[ymd];i;i=g[i].nt)

     if (g[i].v==Hash){ --g[i].sum; return; }

     return;

 }

 il ll calc(RG ull Hash){

     RG int ymd=Hash%wyh;

     for (RG int i=head[ymd];i;i=g[i].nt)

     if (g[i].v==Hash) return g[i].sum;

     return ;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("queue.in","r",stdin);

     freopen("queue.out","w",stdout);

 #endif

     n=gi(),m=gi(),fg=,bin[]=;

     for (RG int i=;i<=;++i) bin[i]=bin[i-]*base;

     for (RG int i=;i<=n;++i){ a[i]=gi(),++tong[a[i]]; if (a[i]!=) fg=; }

     for (RG int i=;i<=n;++i) lst[i]=nxt[i]=i;

     for (RG int p=,op,x,y,k,len;p<=m;++p){

     op=gi();

     if (op==){

         x=gi(),y=gi(),top1=top2=,st1[++top1]=x,st2[++top2]=y;

         for (RG int i=x;top1< && lst[i]!=i;i=lst[i]) st1[++top1]=lst[i];

         for (RG int i=y;top2< && nxt[i]!=i;i=nxt[i]) st2[++top2]=nxt[i];

         RG ull Hsh=; for (RG int i=top1;i;--i) Hsh=Hsh*base+a[st1[i]]; st1[top1+]=;

         for (RG int i=top1;i;--i){

         RG ull Hash=Hsh-a[st1[i+]]*bin[i]; Hsh=Hash,len=i;

         for (RG int j=;j<=top2;++j){

             ++len; if (len>) break;

             Hash=Hash*base+a[st2[j]],add(Hash);

         }

         }

         nxt[x]=y,lst[y]=x;

     }

     if (op==){

         x=gi(),y=nxt[x],top1=top2=,st1[++top1]=x,st2[++top2]=y;

         for (RG int i=x;top1< && lst[i]!=i;i=lst[i]) st1[++top1]=lst[i];

         for (RG int i=y;top2< && nxt[i]!=i;i=nxt[i]) st2[++top2]=nxt[i];

         RG ull Hsh=; for (RG int i=top1;i;--i) Hsh=Hsh*base+a[st1[i]]; st1[top1+]=;

         for (RG int i=top1;i;--i){

         RG ull Hash=Hsh-a[st1[i+]]*bin[i]; Hsh=Hash,len=i;

         for (RG int j=;j<=top2;++j){

             ++len; if (len>) break;

             Hash=Hash*base+a[st2[j]],del(Hash);

         }

         }

         nxt[x]=x,lst[y]=y;

     }

     if (op==){

         scanf("%s",s+),k=gi(),len=strlen(s+),ans=; RG ull Hash;

         if (k==){

         for (RG int i=;i<=len;++i) ans=ans*(ll)tong[s[i]-]%rhl;

         printf("%lld\n",ans); continue;

         }

         for (RG int i=;i<=len;++i) hsh[i]=hsh[i-]*base+s[i]-;

         for (RG int i=;i+k-<=len;++i){

         Hash=hsh[i+k-]-hsh[i-]*bin[k];

         ans=ans*calc(Hash)%rhl;

         }

         printf("%lld\n",ans);

     }

     }

     return ;

 }