#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int type,n,q;
char str[500005];

namespace PAM{
	int s[500005];
	int ch[500005][26],fail[500005],len[500005],occ[500005][26],Mn[500005][26],N;//occ 对应最长出现,Mn 该字符出现距离结尾的最短距离
//	int _ch[20][500005];
	int getnode(int m){
		++N;
		len[N] = m;
		fill(occ[N],occ[N] + 26,1);
		fill(Mn[N],Mn[N] + 26,inf);
		return N;
	}
	void init(){
		memset(s,0x3f,sizeof(s));
		N = -1;
		getnode(0);
		getnode(-1);
		fail[0] = 1;
	}
	inline int getch(int u,int pos){
		return s[pos - len[u]];
	}
	int extend(int p,int pos){//在 p 基础上 extend,当前结尾是 pos
//		printf("extend p=%d pos=%d char=%d\n",p,pos,s[pos]);

		int q = 0;
		if(s[pos - len[p] - 1] == s[pos]) q = p;
		else q = occ[p][s[pos]];

		if(ch[q][s[pos]]) return ch[q][s[pos]];
		ch[q][s[pos]] = getnode(len[q] + 2);
//		printf("q=%d new node %d ",q,N);

		int tq = 0;
		if(s[pos - len[fail[q]] - 1] == s[pos]) tq = fail[q];
		else tq = occ[fail[q]][s[pos]];
		
		if(tq != 1 || len[N] > 1) fail[N] = ch[tq][s[pos]];
//		printf("failp=%d fail=%d\n",fail[p],fail[N]);
		rep(c,0,25){
			occ[N][c] = occ[fail[N]][c];
			Mn[N][c] = Mn[fail[N]][c];
		}
		int c = s[pos - len[fail[N]]];
		occ[N][c] = fail[N];
		if(Mn[N][c] == inf) Mn[N][c] = len[fail[N]];
		return N;
	}
/*	void init(){
		rep(u,0,N) _ch[0][u] = fail[u];
		rep(i,1,19){
			rep(u,0,N) _ch[i][u] = _ch[i - 1][_ch[i - 1][u]];
		}
	}
	int anc(int u,int k){//u 首个长度不超过 k 的祖先
		if(len[u] <= k) return u;

		per(_k,__lg(len[u]),0) if(len[_ch[u][_k]] > k) u = _ch[u][_k];
		return fail[u];
	}*/
	inline int ranking(int u,int c){
		if(Mn[u][c] == inf) return inf;
		int ret = 0;
		rep(cc,0,25) ret += (Mn[u][cc] < Mn[u][c]);
		return ret;
	}
	inline int ranking(int u,int c,int ext){
		if(ext <= 25 && Mn[u][ext] == inf){
			Mn[u][ext] = len[u];
			int ret = ranking(u,c);
			Mn[u][ext] = inf;
			return ret;
		}
		return ranking(u,c);
	}
	inline int value(int u,int c,int ext){
		if(Mn[u][c] != inf) return Mn[u][c];
		if(ext == c) return len[u];
		return inf;
	}
	void dbg(){
		rep(u,0,N){
			printf("node %d len %d fail %d\n",u,len[u],fail[u]);
			rep(c,0,25) if(ch[u][c]) printf("%c->%d\n",c + 'a',ch[u][c]);
		}
		printf("Mn info\n");
		rep(u,0,N){
			printf("node %d\n",u);
			rep(c,0,25) if(Mn[u][c] != inf) printf("%c:%d\n",c + 'a',Mn[u][c]);
		}
	}
}

int I[500005],dep[500005],_fa[500005],ext[500005],N;
struct node{
	int ch[26],u,fail;//u 这个点的最长回文后缀在 pam 上的对应节点
}tree[500005];
vector <int> SS[500005];
int idx[500005];

int ins(int m){
	int u = 0;
	rep(i,1,m){
		if(!tree[u].ch[str[i] - 'a']){
			tree[u].ch[str[i] - 'a'] = ++N;
			dep[N] = i;_fa[N] = u;
		}
		u = tree[u].ch[str[i] - 'a'];
	}
	return u;
}

int extend(int u,char c){
	if(!tree[u].ch[c - 'a']){
		tree[u].ch[c - 'a'] = ++N;
		dep[N] = dep[u] + 1;_fa[N] = u;
	}
	return tree[u].ch[c - 'a'];
}

void dfs(int u){
	rep(c,0,25){
		int v = tree[u].ch[c];
		if(!v) continue;
		PAM::s[dep[v]] = c;
		tree[v].u = PAM::extend(tree[u].u,dep[v]);
		ext[v] = PAM::getch(tree[v].u,dep[v]);
		dfs(v);
	}
}
int _ch[500005][26],_sp[500005],cov[500005];//sp 出边,接一个字符 c rank=i 的最浅祖先出边,_sp 最浅的祖先,有啥也不是的出边
int to[20][500005];
queue <int> Q;
void psh(int u){
	Q.push(u);
	int p = tree[u].fail;
	if(!cov[idx[u]]){
		rep(c,0,25) _ch[idx[u]][c] = _ch[idx[p]][c];
		_sp[idx[u]] = _sp[idx[p]];		
		cov[idx[u]] = 1;
	}

	rep(c,0,25){
		int v = tree[u].ch[c];
		if(!v) continue;
		int temp = PAM::ranking(tree[u].u,c,ext[u]);
		if(temp != inf) _ch[idx[u]][temp] = v;
		else _sp[idx[u]] = v;
	}

//	printf("upd %d\n",idx[u]);
//	rep(c,0,25) if(_ch[idx[u]][c] != -1) printf("ranking=%d %d\n",c,_ch[idx[u]][c]);
	to[0][u] = tree[u].fail;
	rep(k,1,19) to[k][u] = to[k - 1][to[k - 1][u]];
}

int anc(int u,int k){
	if(dep[u] <= k) return u;
	per(_k,__lg(dep[u]),0) if(dep[to[_k][u]] > k) u = to[_k][u];
	return to[0][u];
}

void build(){
	_sp[0] = -1;
	rep(c,0,25) _ch[0][c] = -1;
	rep(c,0,25){
		if(!tree[0].ch[c]) continue;
		_sp[0] = tree[0].ch[c];
		psh(tree[0].ch[c]);
	}

	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		rep(c,0,25){
			int v = tree[u].ch[c];
			if(!v) continue;
			int p = tree[u].fail,inst = PAM::ranking(tree[u].u,c,ext[u]);
//			printf("fail %d p=%d (%d,%d,%d) ranking inst=%d idx[p]=%d\n",v,p,tree[u].u,c,ext[u],inst,idx[p]);

//			if(inst != inf) printf("inst=%d %d %d_ch=%d\n",inst,idx[p],inst,_ch[idx[p]][inst]);
			if(inst != inf && _ch[idx[p]][inst] != -1){
				tree[v].fail = _ch[idx[p]][inst];
//				printf("fix %d %d\n",v,tree[v].fail);
			}else{
				p = anc(p,PAM::value(tree[u].u,c,ext[u]));
				tree[v].fail = _sp[idx[p]];
			}
//			printf("get result=%d\n",tree[v].fail);
			psh(v);
		}
	}
}

void putstr(){
	printf("ACAM str\n");
	rep(u,0,N){
		printf("node %d dep %d u=%d fail %d\n",u,dep[u],tree[u].u,tree[u].fail);
		rep(c,0,25) if(tree[u].ch[c]) printf("%c %d\n",c + 'a',tree[u].ch[c]);
	}
}

bool cmp(int x,int y){
	if(idx[_fa[x]] != idx[_fa[y]]) return idx[_fa[x]] < idx[_fa[y]];
	return PAM::len[tree[x].u] < PAM::len[tree[y].u];
}

vector <int> son[500005];
int NN,dfn[500005],siz[500005];
void dfs2(int u){
	dfn[u] = ++NN;
	siz[u] = 1;
	for(int v:son[u]){
		dfs2(v);
		siz[u] += siz[v];
	}
}
vector <pii> QQ[500005];
int result[500005];

#define lowbit(x) (x & (-x))
int _tree[500005];
void upd(int pos,int C){
	while(pos <= NN){
		_tree[pos] += C;
		pos += lowbit(pos);
	}
}

int qry(int pos){
	int ret = 0;
	while(pos){
		ret += _tree[pos];
		pos -= lowbit(pos);
	}
	return ret;
}

void dfs3(int u){
	upd(dfn[idx[u]],1);
	for(pii II:QQ[u]) result[II.second] = qry(dfn[II.first] + siz[II.first] - 1) - qry(dfn[II.first] - 1);

	rep(c,0,25){
		int v = tree[u].ch[c];
		if(!v) continue;
		dfs3(v);
	}
	upd(dfn[idx[u]],-1);
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d%d",&type,&n,&q);
	rep(i,1,n){
		if(!type){
			scanf("%s",str + 1);
			int m = strlen(str + 1);
			I[i] = ins(m);
		}else{
			int prv;
			scanf("%d%s",&prv,str + 1);
			I[i] = extend(I[prv],str[1]);
		}
	}
	PAM::init();
	dfs(0);
//	PAM::dbg();


	rep(u,0,N) SS[dep[u]].eb(u);
	rep(i,1,N){
		if(SS[i].empty()) continue;
		sort(SS[i].begin(),SS[i].end(),cmp);
		int cur = -1;
		for(int u:SS[i]){
			if(cur == -1 || idx[_fa[u]] != idx[_fa[cur]] || PAM::len[tree[cur].u] != PAM::len[tree[u].u]) cur = u;
			idx[u] = cur;
		}
	}
//	printf("idxqwq\n");
//	rep(u,0,N) printf("%d ",idx[u]);
//	printf("\n");
	build();
//	putstr();

	rep(u,1,N) if(idx[u] == u) son[idx[tree[u].fail]].eb(u);
	dfs2(0);

	rep(i,1,q){
		int x,y;
		scanf("%d%d",&x,&y);
		QQ[I[y]].eb(mkp(idx[I[x]],i));
	}
	dfs3(0);
	rep(i,1,q) printf("%d\n",result[i]);
	return 0;
}