#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
#include<iostream>
#include<bitset>
#include<functional>
#include<numeric>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<cmath>
#include<random>
#include<ctime>
#include<complex>
using namespace std;
typedef long long LL;
mt19937 gene(233);
typedef complex<double> Complex;
#define fi first
#define se second
#define ins insert
#define pb push_back
inline char GET_CHAR(){
    const int maxn = 131072;
    static char buf[maxn],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
}
inline int getInt() {
    int res(0);
    char c = getchar();
    while(c < '0') c = getchar();
    while(c >= '0') {
        res = res * 10 + (c - '0');
        c = getchar();
    }
    return res;
}

inline int fastpo(int x, int n, int mod) {
    int res(1);
    while(n) {
        if(n & 1) {
            res = res * (LL)x % mod;
        }
        x = x * (LL) x % mod;
        n /= 2;
    }
    return res;
}

inline string itoa(int x, int width = 0) {
  string res;
  if(x == 0) res.push_back('0');
  while(x) {
    res.push_back('0' + x % 10);
    x /= 10;
  }
  while((int)res.size() < width) res.push_back('0');
  reverse(res.begin(), res.end());
  return res;
}

const int N = 1000033;
const int LOG = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int A = 26;
int sons[N][A], siz[N], fa[N], lst[N];
const int MAXM = 2000010;
struct SAM {
    int tot, root, lst, mom[MAXM], mx[MAXM];
    int ans[MAXM], ind[MAXM], acc[MAXM], nxt[MAXM][A];
    int newNode() {
        int res = ++tot;
        fill(nxt[res], nxt[res] + A, 0);
        mom[res] = mx[res] = acc[res] = 0;
        return res;
    }
    void init() {
        tot = 0;
        root = newNode();
        mom[root] = 0, mx[root] = 0;
        lst = root;
    }
    int push(int lst, int c) {
        int p = lst;
        int np = nxt[p][c] ? 0 : newNode();
        mx[np] = mx[p] + 1;
        for(;  p && nxt[p][c] == 0; p = mom[p])
            nxt[p][c] = np;
        if(p == 0) mom[np] = root;
        else {
            int q = nxt[p][c];
            if(mx[p] + 1 == mx[q]) mom[np] = q;
            else {
                int nq = newNode();
                mx[nq] = mx[p] + 1;
                for(int i = 0; i < A; i++) {
                    nxt[nq][i] = nxt[q][i];
                }
                mom[nq] = mom[q];
                mom[q] = nq;
                mom[np] = nq;
                for(; p && nxt[p][c] == q; p = mom[p]) nxt[p][c] = nq;
            }
        }
        int res = np ? np : mom[np];
        ans[res]++;
        return res;
    }
    int calc(char * st) {
        int p = 1;
        for(int j = strlen(st) - 1; j >= 0; j--) {
            int c = st[j] - 'A';
            if(nxt[p][c]) {
                p = nxt[p][c];
            }else  return 0;
        }
        return ans[p];
    }
    void calcdp() {
        for(int i = 1; i <= tot; i++) {
            for(int c = 0; c < A; c++) {
                //printf("ic %d %d\n", i, c);
                if(nxt[i][c]) {
                    ind[nxt[i][c]]++;
                    printf("!%d %d %d\n", i, c, nxt[i][c]);
                }
            }
        }
        vector<int> q;
        for(int i = 1; i <= tot; i++) {
            printf("%d %d\n", i, ind[i]);
            if(ind[i] == 0) {
            q.pb(i);
        }
        }
        for(int op = 0; op < (int)q.size(); op++)  {
            int v = q[op];
            for(int c = 0; c < A; c++) {
                int y = nxt[v][c];
                if(y != 0) --ind[y];
                if(y != 0 && ind[y] == 0) {
                    q.push_back(y);
                }
            }
        }
        for(int op = tot - 1; op >= 0; op--) {
            int v = q[op];
            for(int c = 0;c < A; c++) {
                int y = nxt[v][c];
                if(y) ans[v] += ans[y];
            }
        }
    }
} sam;
int main() {
    int n, k;
    sam.init();
    scanf("%d%d", &n, &k);
    for(int i(1); i <= n; i++) {
        static char st[11];
        int p;
        scanf("%s%d", st, &p);
        sam.push(lst[p], st[0] - 'A');
    }
    sam.calcdp();
    for(int i = 1; i <= k; i++) {
        static char st[N];
        scanf("%s", st);
        printf("%d\n", sam.calc(st));
    }
}