Description：

给 $n$ 个字符串，支持在某个串后面插入字符，询问第 $x$ 个字符串在第 $y$ 次操作后在当前的 $z$ 中的出现次数， $n$ 个串本质不同的子串个数，给字符串 $T$ 求在 $n$ 个字符串中出现次数最多是多少。

$1\leqslant n\leqslant 20，1\leqslant q,\sum |S|\leqslant2\times 10^5$

Solution：

建出广义后缀自动机并用 $LCT$ 维护 $Right$ 集合，对于每个串记一下第 $i$ 次操作后在什么位置，然后就都可以求了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,t,m;

#define MAXN 21 

#define MAXL 400010

char c[MAXL],ct[20000010];

#define I inline

#define R register

namespace LCT

{

	struct node

	{

		int c[2],fa;

		int tag[MAXN],val[MAXN];

		bool rev;

		node()

		{

			memset(tag,0,sizeof(tag));

			memset(val,0,sizeof(val));

		}

	}t[MAXL << 1];

	I int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

	I bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

	I void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

	I void pushdown(int rt)

	{

		for(R int i = 1;i <= n;++i)

		{

			if(t[rt].tag[i] != 0)

			{

				t[t[rt].c[0]].tag[i] += t[rt].tag[i];t[t[rt].c[0]].val[i] += t[rt].tag[i];

				t[t[rt].c[1]].tag[i] += t[rt].tag[i];t[t[rt].c[1]].val[i] += t[rt].tag[i];

				t[rt].tag[i] = 0;

			}

		}

		if(t[rt].rev)

		{

			t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

			swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

		}

		return;

	}

	I void rotate(int x)

	{

		R int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

		if(!isroot(y))t[z].c[fy] = x;

		t[x].fa = z;

		connect(t[x].c[fx ^ 1],y,fx);

		connect(y,x,fx ^ 1);

		return;

	}

	int stack[MAXL << 1],top = 0;

	I void splay(int x)

	{

		stack[++top] = x;

		for(R int i = x;!isroot(i);i = t[i].fa)stack[++top] = t[i].fa;

		while(top > 0)pushdown(stack[top--]);

		while(!isroot(x))

		{

			R int y = t[x].fa;

			if(isroot(y)){rotate(x);break;}

			if(id(x) == id(y)){rotate(y);rotate(x);}

			else{rotate(x);rotate(x);}

		}

		return;

	}

	I void access(int k){for(R int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;}return;}

	I void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

	I void link(int a,int b){makeroot(a);t[a].fa = b;return;}

	I void split(int a,int b){makeroot(a);access(b);splay(b);return;}

	I void cut(int a,int b){split(a,b);t[a].fa = t[b].c[0] = 0;return;}

	I void addtag(int rt,int id,int v){t[rt].val[id] += v;t[rt].tag[id] += v;return;}

	I void add(int a,int b,int id,int v){split(a,b);addtag(b,id,v);return;}

}

namespace SAM

{

	struct node

	{

		int tr[10],par,maxl;

	}s[MAXL << 1];

	int ptr = 1,root = 1;

	I int newnode(int l){R int k = ++ptr;s[k].maxl = l;return k;}

	int pos[MAXN][MAXL];

	int l[MAXN];

	long long sum = 0;

	int v[MAXN];

	I void scut(int k,int f)

	{

		LCT::splay(k);

		for(R int i = 1;i <= n;++i)v[i] = LCT::t[k].val[i];

		LCT::split(1,f);

		for(R int i = 1;i <= n;++i)LCT::addtag(f,i,-v[i]);

		LCT::cut(k,f);

		return;

	}

	I void slink(int k,int f)

	{

		LCT::splay(k);

		for(R int i = 1;i <= n;++i)v[i] = LCT::t[k].val[i];

		LCT::split(1,f);

		for(R int i = 1;i <= n;++i)LCT::addtag(f,i,v[i]);

		LCT::link(k,f);

		return;

	}

	I int extend(int k,int last,int id)

	{

		R int p = last;

		if(s[p].tr[k] != 0)

		{

			R int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)

			{

				LCT::add(1,q,id,1);

				return q;

			}

			else

			{

				R int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				scut(q,s[q].par);

				s[nq].par = s[q].par;

				slink(nq,s[q].par);

				s[q].par = nq;slink(q,nq);

				LCT::add(1,nq,id,1);

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

				return nq;

			}

		}

		else

		{

			R int np = newnode(s[p].maxl + 1);

			for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

			if(p == 0)

			{

				s[np].par = root;

				slink(np,root);

			}

			else

			{

				R int q = s[p].tr[k];

				if(s[p].maxl + 1 == s[q].maxl)

				{

					s[np].par = q;

					slink(np,q);

				}

				else

				{

					R int nq = newnode(s[p].maxl + 1);

					memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

					scut(q,s[q].par);

					s[nq].par = s[q].par;slink(nq,s[q].par);

					s[q].par = s[np].par = nq;

					slink(q,nq);slink(np,nq);

					for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

				}

			}

			LCT::add(1,np,id,1);

			sum += s[np].maxl - s[s[np].par].maxl;

			return np;

		}

	}

	I int getright(int k,int id)

	{

		LCT::splay(k);

		return LCT::t[k].val[id]; 

	}

}

int main()

{

	n = rd();t = rd();

	for(R int i = 1;i <= n;++i)

	{

		SAM::pos[i][0] = 1;

		scanf("%s",c + 1);

		SAM::l[i] = strlen(c + 1);

		for(R int k = 1;k <= SAM::l[i];++k)SAM::pos[i][0] = SAM::extend(c[k] - '0',SAM::pos[i][0],i);

	}

	scanf("%d",&m);

	R int op,x,y,z;

	R int lastans = 0;

	for(R int i = 1;i <= m;++i)

	{

		op = rd();

		for(R int p = 1;p <= n;++p)SAM::pos[p][i] = SAM::pos[p][i - 1];

		if(op == 1)

		{

			x = rd();y = rd();

			y = (y ^ (lastans * t)) % 10;

			++SAM::l[x];

			SAM::pos[x][i] = SAM::extend(y,SAM::pos[x][i],x);

		}

		if(op == 2)

		{

			x = rd();y = rd();z = rd();

			lastans = SAM::getright(SAM::pos[x][y],z);

			printf("%d\n",lastans);

		}

		if(op == 3)

		{

			printf("%lld\n",SAM::sum);

		}

		if(op == 4)

		{

			scanf("%s",ct + 1);

			R int len = strlen(ct + 1);

			R int cur = SAM::root;

			R bool tag = true;

			for(R int i = 1;i <= len;++i)

			{

				if(SAM::s[cur].tr[ct[i] - '0'] == 0){tag = false;break;}

				else cur = SAM::s[cur].tr[ct[i] - '0'];

			}

			R int res = 0;

			LCT::splay(cur); 

			if(tag)for(R int i = 1;i <= n;++i)res = max(res,LCT::t[cur].val[i]);

			lastans = res;

			printf("%d\n",res);

		}

	}

	return 0;

}