#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 200006

#define ll long long

#define lson t[x].ch[0]

#define rson t[x].ch[1]

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

struct data

{

    int tim,id;

    data(int tim=0,int id=0):tim(tim),id(id){}

};

struct node

{

    int ch[2],f,val[21],tag[21];

}t[N<<1];

ll sub;

int lastans;

char str[N];

int last,tot,n;

vector<data>G[21];

int ch[N<<1][11],pre[N<<1],len[N<<1],sta[N<<1];

inline int get(int x)

{

    return t[t[x].f].ch[1]==x;

}

inline int isrt(int x)

{

    return !(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x);

}

inline void mark(int x,int p,ll v)

{

    t[x].val[p]+=v,t[x].tag[p]+=v;

}

void pushdown(int x)

{

    if(!x) return;

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

    {

        if(t[x].tag[i])

        {

            if(lson)   mark(lson,i,t[x].tag[i]);

            if(rson)   mark(rson,i,t[x].tag[i]);

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

        }

    }

}

void rotate(int x)

{

    int old=t[x].f,fold=t[old].f,which=get(x);

    if(!isrt(old))    t[fold].ch[t[fold].ch[1]==old]=x;

    t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old;

    t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;

}

void splay(int x)

{

    int u=x,fa,v=0;

    for(sta[++v]=u;!isrt(u);u=t[u].f)    sta[++v]=t[u].f;

    for(;v;--v)    pushdown(sta[v]);

    for(u=t[u].f;(fa=t[x].f)!=u;rotate(x))

        if(t[fa].f!=u)     rotate(get(fa)==get(x)?fa:x);

}

void Access(int x)

{

    for(int y=0;x;y=x,x=t[x].f)

    {

        splay(x);

        rson=y;

    }

}

// y 无父亲

void link(int x,int y)

{

    t[y].f=x;

}

// x 是 y 的父亲

void cut(int x,int y)

{

    Access(y),splay(y);

    t[t[y].ch[0]].f=0;

    t[y].ch[0]=0;

}

void extend(int id,int c)

{

    if(ch[last][c])

    {

        int p=last;

        int q=ch[p][c];

        if(len[q]==len[p]+1)   last=q;

        else

        {

            int nq=++tot;

            len[nq]=len[p]+1;

            memcpy(ch[nq],ch[q],sizeof(ch[q]));

            cut(pre[q],q);

            for(int j=1;j<=n;++j)  t[nq].val[j]=t[q].val[j];

            link(pre[q],nq);

            link(nq,q);

            pre[nq]=pre[q],pre[q]=nq;

            for(;p&&ch[p][c]==q;p=pre[p])    ch[p][c]=nq;

            last=nq;

        }

    }

    else

    {

        int np=++tot,p=last;

        len[np]=len[p]+1,last=np;

        for(;p&&!ch[p][c];p=pre[p])    ch[p][c]=np;

        if(!p)   pre[np]=1,link(1,np);

        else

        {

            int q=ch[p][c];

            if(len[q]==len[p]+1)   pre[np]=q,link(q,np);

            else

            {

                int nq=++tot;

                len[nq]=len[p]+1;

                memcpy(ch[nq],ch[q],sizeof(ch[q]));

                cut(pre[q],q);

                for(int j=1;j<=n;++j)  t[nq].val[j]=t[q].val[j];

                link(pre[q],nq);

                link(nq,q);

                link(nq,np);

                pre[nq]=pre[q],pre[q]=pre[np]=nq;

                for(;p&&ch[p][c]==q;p=pre[p])    ch[p][c]=nq;

            }

        }

        sub+=len[np]-len[pre[np]];

    }

    Access(last),splay(last),mark(last,id,1ll);

}

int main()

{

    // setIO("input");

    int i,j,ty,m;

    scanf("%d%d",&n,&ty);

    for(tot=i=1;i<=n;++i)

    {

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

        int len=strlen(str+1);

        for(last=j=1;j<=len;++j)   extend(i,str[j]-'0');

        G[i].push_back(data(0,last));

    }

    scanf("%d",&m);

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

    {

        int op,x,y,z;

        scanf("%d",&op);

        if(op==1)

        {

            scanf("%d%d",&x,&y);

            y=(y^(lastans*1ll*ty))%10;

            last=G[x][G[x].size()-1].id;

            extend(x,y);

            G[x].push_back(data(i,last));

        }

        if(op==2)

        {

            scanf("%d%d%d",&x,&y,&z);

            int l=0,r=G[x].size()-1,mid=0,pp=0;

            while(l<=r)

            {

                mid=(l+r)>>1;

                if(G[x][mid].tim<=y)    pp=G[x][mid].id,l=mid+1;

                else r=mid-1;

            }

            Access(pp),splay(pp);

            printf("%d\n",lastans=t[pp].val[z]);

        }

        if(op==3)

        {

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

        }

        if(op==4)

        {

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

            int len=strlen(str+1),pp=1,flag=0;

            for(j=1;j<=len;++j)

            {

                if(ch[pp][str[j]-'0'])   pp=ch[pp][str[j]-'0'];

                else { flag=1;break; }

            }

            // 能匹配

            if(!flag)

            {

                Access(pp);

                int best=0;

                for(j=1;j<=n;++j)    best=max(best,t[pp].val[j]);

                lastans=best;

            }

            else lastans=0;

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

        }

    }

    return 0;

}