扔个很丑的模板...
#include<bits/stdc++.h>
using namespace std;
long long n,m,op,p,mod=998244353,l[200010],r[200010],ls[200010],rs[200010],q[10000010],lin[10000010],len=0,tail=0;
unsigned long long seven[60],a[200010];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct one
{
long long sum;
unsigned long long val;
int next;
};
one e[10001000];
void insert(unsigned long long p,int p2)
{
e[++len].next=lin[p2];
lin[p2]=len;
e[len].sum=1;
e[len].val=p;
}
void add(unsigned long long p)
{
int tt=p%10000000;
for(int i=lin[tt];i;i=e[i].next)if(e[i].val==p){e[i].sum++;return;}
insert(p,tt);
}
void fadd(unsigned long long p)
{
int tt=p%10000000;
for(int i=lin[tt];i;i=e[i].next)if(e[i].val==p){e[i].sum--;return;}
}
int getsum(unsigned long long p)
{
int tt=p%10000000;
for(int i=lin[tt];i;i=e[i].next)if(e[i].val==p){return e[i].sum;}
return 0;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){a[i]=read();add(a[i]);l[i]=r[i]=i;}
seven[0]=1;for(int i=1;i<=50;i++)seven[i]=seven[i-1]*7;
while(m--)
{
op=read();
int x,y;
if(op==1)
{
x=read();y=read();
int tx=x,ty=y;
unsigned long long ans=0;
for(int i=0;i<49;i++)
{
ans+=seven[i]*a[tx];unsigned long long sum=ans;ty=y;
for(int j=0;j<49-i;j++)
{
sum*=7;sum+=a[ty];add(sum);
if(r[ty]==ty)break;ty=r[ty];
}
if(tx==l[tx])break;tx=l[tx];
}
r[x]=y;l[y]=x;
}
else if(op==2)
{
x=read();
y=r[x];
int tx=x,ty=y;
unsigned long long ans=0;
for(int i=0;i<49;i++)
{
ans+=seven[i]*a[tx];
unsigned long long sum=ans;
ty=y;
for(int j=0;j<49-i;j++)
{
sum*=7;sum+=a[ty];fadd(sum);
if(r[ty]==ty)break;ty=r[ty];
}
if(tx==l[tx])break;tx=l[tx];
}
r[x]=x;l[y]=y;
}
else
{
unsigned long long p=0;long long ans=1;tail=0;char ch=getchar();
while(ch<'1'||ch>'6')ch=getchar();
while(ch<='6'&&ch>='1'){q[++tail]=ch-'0';ch=getchar();}x=read();
for(int i=1;i<=x;i++){p*=7;p+=q[i];}ans*=getsum(p);ans%=mod;
for(int i=x+1;i<=tail;i++){p-=seven[x-1]*q[i-x];p*=7;p+=q[i];ans*=getsum(p);ans%=mod;}
printf("%lld
",ans);
}
}
return 0;
}