#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7, A = 26;

struct SA {
    struct node {
        int to[26];
        int link, len;
        ll co = 0;

        node() {
            memset(to, 0, sizeof to);
            co = 0, link = 0, len = 0;
        }
    };

    int last, sz;
    vector<node> v;

    SA(int n) {
        v = vector<node>(n + 1);
        last = 0, sz = n + 1;
    }

    void add_letter(int c, int l, int p) {
        int last=l;

        v[last].len = v[p].len + 1;
        v[last].co = 1;
        for (; v[p].to[c] == 0; p = v[p].link)
            v[p].to[c] = last;
        if (v[p].to[c] == last) {
            v[last].link = 0;
            return;
        }
        int q = v[p].to[c];
        if (v[q].len == v[p].len + 1) {
            v[last].link = q;
            return;
        }
        int cl = sz++;
        v.push_back(v[q]);
        v.back().co = 0;
        v.back().len = v[p].len + 1;
        v[last].link = v[q].link = cl;

        for (; v[p].to[c] == q; p = v[p].link)
            v[p].to[c] = cl;
    }

    void build_co() {
        priority_queue<pair<int, int>> q;
        for (int i = sz - 1; i > 0; i--)
            q.push({v[i].len, i});
        while (q.size()) {
            int i = q.top().second;
            q.pop();
            v[v[i].link].co += v[i].co;
        }
    }
};

SA *sa;

ll solve(string s) {
    reverse(s.begin(), s.end());
    int cur = 0;
    for (auto ch: s) {
        if (sa->v[cur].to[ch - 'A'] == 0)return 0;
        cur = sa->v[cur].to[ch - 'A'];
    }
    return sa->v[cur].co;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    sa = new SA(n);
    for (int i = 0; i < n; ++i) {
        char x;
        int p;
        cin >> x >> p;
        x -= 'A';
        sa->add_letter(x,i+1, p);
    }
    sa->build_co();
    while (q--) {
        string s;
        cin >> s;
        cout << solve(s) << '\n';
    }


    return 0;
}