#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
	int ch = 0, f = 0; x = 0;
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
	if(f) x = -x;
}
const int N = 2000005;
char s[N];
int n, m;
namespace AC{
	vector<int> g[N];
	queue<int> q;
	int ch[N][26], tr[N][26], fa[N], sum[N], pos[N], size = 1;
	inline void init(int n){
		for(int i = 1, x; i <= n; i++){
			sum[++size] = 1;
			int c = getchar() - 'A';
			read(x);
			ch[x+1][c] = size;
		}
	}
	inline void ins(char *str, int id){
		int n = strlen(str + 1), p = 1;
		for(int i = n; i >= 1; i--){
			int c = str[i] - 'A';
			if(!ch[p][c]) ch[p][c] = ++size;
			p = ch[p][c];
		}
		pos[id] = p;
	}
	inline void build(){
		for(int i = 0; i < 26; i++) tr[0][i] = 1;
		for(q.push(1); !q.empty(); q.pop()){
			int u = q.front();
			for(int i = 0; i < 26; i++){
				if(ch[u][i]){
					int v = ch[u][i];
					tr[u][i] = v;
					fa[v] = tr[fa[u]][i];
					q.push(v);
				}
				else tr[u][i] = tr[fa[u]][i];
			}
		}
		for(int i = 2; i <= size; i++)
			g[fa[i]].push_back(i);
	}
	inline void dfs(int u){
		for(auto v : g[u]) dfs(v), sum[u] += sum[v];
	}
}

int main(){
	read(n), read(m);
	AC::init(n);
	for(int i = 1; i <= m; i++){
		scanf("%s", s + 1);
		AC::ins(s, i);
	}
	AC::build();
	AC::dfs(1);
	for(int i = 1; i <= m; i++)
		printf("%d\n", AC::sum[AC::pos[i]]);
	return 0;
}