#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define ll long long

#define N 500010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

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

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,k,fail[N],len[N],id[N],q[N],p[N],tmp[N],f[N],root[N],cnt,last,tot;

ll ans[N];

char s[N];

map<int,int> son[N];

struct data{int l,r,x;

}tree[N<<4];

int newnode(){cnt++;son[cnt].clear();fail[cnt]=len[cnt]=0;return cnt;}

void extend(int c)

{

    int x=newnode(),p=last;last=x;len[x]=len[p]+1;id[len[x]]=x;

    while (!son[p][c]&&p) son[p][c]=x,p=fail[p];

    if (!p) fail[x]=1;

    else

    {

        int q=son[p][c];

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

        else

        {

            int y=newnode();

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

            son[y]=son[q];

            fail[y]=fail[q],fail[q]=fail[x]=y;

            while (son[p][c]==q) son[p][c]=y,p=fail[p];

        }

    }

}

void ins(int &k,int l,int r,int x)

{

	tree[++tot]=tree[k],k=tot;tree[k].x++;

	if (l==r) return;

	int mid=l+r>>1;

	if (x<=mid) ins(tree[k].l,l,mid,x);

	else ins(tree[k].r,mid+1,r,x);

}

int merge(int x,int y,int l,int r)

{

	if (!x||!y) return x|y;

	int k=++tot;tree[k].x=tree[x].x+tree[y].x;

	if (l<r)

	{

		int mid=l+r>>1;

		tree[k].l=merge(tree[x].l,tree[y].l,l,mid);

		tree[k].r=merge(tree[x].r,tree[y].r,mid+1,r);

	}

	else tree[k].l=tree[k].r=0;

	return k;

}

int query(int k,int l,int r,int x)

{

	if (l==r) return l;

	int mid=l+r>>1;

	if (tree[tree[k].l].x>=x) return query(tree[k].l,l,mid,x);

	else return query(tree[k].r,mid+1,r,x-tree[tree[k].l].x);

}

int main()

{

#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	while (scanf("%d%d%d",&n,&m,&k)!=EOF)

	{

		scanf("%s",s+1);cnt=0,last=1;newnode();

		for (int i=1;i<=n;i++) extend(s[i]-'a');int t=0;

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

		{

			int op=read();

			if (op==1) n++,extend(getc()-'a');

			else q[++t]=n;

		}

		for (int i=1;i<=n;i++) tmp[i]=0;

		for (int i=1;i<=cnt;i++) tmp[len[i]]++;

		for (int i=1;i<=n;i++) tmp[i]+=tmp[i-1];

		for (int i=1;i<=cnt;i++) p[tmp[len[i]]--]=i;

		for (int i=1;i<=n;i++) ans[i]=0;tot=0;

		for (int i=0;i<=cnt;i++) root[i]=0;

		for (int i=1;i<=n;i++) ins(root[id[i]],1,n,i);

		for (int i=cnt;i>=1;i--)

		{

			int x=p[i];

			if (tree[root[x]].x>=k) ans[query(root[x],1,n,k)]+=len[x]-len[fail[x]];

			root[fail[x]]=merge(root[fail[x]],root[x],1,n);

		}

		for (int i=1;i<=n;i++) ans[i]+=ans[i-1];

		for (int i=1;i<=t;i++) printf("%I64d\n",ans[q[i]]);

	}

	return 0;

}