#include <queue>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

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

#define maxn 800000

#define N 10

#define ll long long

using namespace std;

char str[maxn];

long long cur_ans;

struct Link_Cut_Tree{

    int ch[maxn][2],f[maxn],tag[maxn],sta[maxn],val[maxn];

    int get(int x) {return ch[f[x]][1]==x; }

    int which(int x){ return ch[f[x]][1]==x;}

    int isRoot(int x){ return !(ch[f[x]][1]==x||ch[f[x]][0]==x);}

    int lson(int x){ return ch[x][0];}

    int rson(int x){return ch[x][1];}

    void add(int x,int delta){if(!x)return;val[x]+=delta,tag[x]+=delta;}

    void pushdown(int x){if(tag[x]) add(lson(x),tag[x]),add(rson(x),tag[x]),tag[x]=0;}

    void rotate(int x){

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

        if(!isRoot(old)) ch[fold][ch[fold][1]==old]=x;

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

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

    }

    void splay(int x){

        int v=0,u=x;

        sta[++v]=u;

        while(!isRoot(u)) sta[++v]=f[u],u=f[u];

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

        u=f[u];

        for(int fa;(fa=f[x])!=u && x;rotate(x))

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

    }

    void Access(int x){

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

            splay(x),ch[x][1]=y;

    }

    void link(int a,int b){

        Access(a),splay(a),add(a,val[b]),f[b]=a;

    }

    void cut(int b){

        Access(b),splay(b);

        add(lson(b),-val[b]),f[lson(b)]=ch[b][0]=0;

    }

}tree;

struct SAM{

    int ch[maxn][10],f[maxn],dis[maxn];

    int tot,last;

    void init(){ last=tot=1; }

    int ins(int c){

        int p=last,np=++tot; last=np; dis[np]=dis[p]+1;tree.val[np]=tree.tag[np]=1;

        while(p&&!ch[p][c])ch[p][c]=np,p=f[p];

        if(!p) f[np]=1,tree.link(1,np);

        else{

            int q=ch[p][c],nq;

            if(dis[q]==dis[p]+1)f[np]=q,tree.link(q,np);

            else{

                nq=++tot;

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

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

                f[nq]=f[q];

                tree.link(f[q],nq),tree.cut(q),tree.link(nq,q),tree.link(nq,np);

                f[q]=f[np]=nq;

                while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];

            }

        }

        cur_ans+=dis[np] - dis[f[np]];

        return np;

    }

}sam;

struct Node{

    int u,c;

    Node(int u=0,int c=0):u(u),c(c){}

};

queue<int>Q;

vector<int>mark;

vector<Node>G[maxn];

int idx[maxn];

void DFS(int u,int fa){

    int k=G[u].size();

    for(int i=0;i<k;++i){

        Node j=G[u][i];

        if(j.u==fa) continue;

        sam.last=idx[u],idx[j.u]=sam.ins(j.c);

        DFS(j.u,u);

    }

    G[u].clear();

}

void build_Tree(int n,int st){

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

        int u,v;

        char c[10];

        scanf("%d%d",&u,&v);

        scanf("%s",c);

        G[u].push_back(Node(v,c[0]-'a'));

        G[v].push_back(Node(u,c[0]-'a'));

    }

    DFS(st,0);

}

int main(){

    //setIO("input");

    int lll,n,m;

    scanf("%d",&lll);

    sam.init(),idx[1] = 1;             

    scanf("%d",&n);

    build_Tree(n,1); 

    scanf("%d",&m); 

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

        int opt_idx,a,b;

        scanf("%d",&opt_idx);

        if(opt_idx==1)  printf("%lld\n",cur_ans);

        if(opt_idx==2) {

            scanf("%d%d",&a,&b);

            build_Tree(b,a);

        }

        if(opt_idx==3) {

            scanf("%s",str);

            a=strlen(str);

            b=1;

            bool flag = 0;

            for(int j=0;j<a;++j) {

                b=sam.ch[b][str[j]-'a'];

                if(!b)  flag = 1;

            }

            if(flag) printf("0\n");

            else {

                tree.Access(b);

                tree.splay(b);

                printf("%d\n",tree.val[b]);

            }

        }

    }

    return 0;

}