JOI '16 Open P

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;

// mot node cua cay trie
struct node
{
    node *child[4];
    vector<int> listOfString;
    node()
    {
        for (int i = 0; i < 4; ++i)
            child[i] = NULL;
    }
};

#define all(x) (x).begin(), (x).end()

int Map(const char &x)
{
    switch (x)
    {
    case 'A':
        return 0;
    case 'U':
        return 1;
    case 'G':
        return 2;
    case 'C':
        return 3;
    default:
        return -1;
    }
}

// Cay trie
struct Trie
{
    node root;

    void Add(const string &s, const int &v)
    {
        node *a = &root;
        int id = 0;

        while (id <= (int)s.size())
        {
            a->listOfString.emplace_back(v);

            if (id == (int)s.size())
                break;

            if (!(a->child[Map(s[id])]))
                a->child[Map(s[id])] = new node;

            a = a->child[Map(s[id])];
            ++id;
        }
    }

    pair<int, int> Get(const string &s)
    {
        node *a = &root;
        int id = 0;

        while (id <= (int)s.size())
        {
            if (id == (int)s.size())
                return make_pair(a->listOfString[0], a->listOfString.back());

            if (!(a->child[Map(s[id])]))
                return make_pair(-1, -1);

            a = a->child[Map(s[id])];

            ++id;
        }

        return make_pair(-1, -1);
    }

    int Cal(const string &s, const int &l, const int &r)
    {
        node *a = &root;
        int id = 0;

        while (id <= (int)s.size())
        {
            if (id == (int)s.size())
                return upper_bound(all(a->listOfString), r) - lower_bound(all(a->listOfString), l);

            if (!(a->child[Map(s[id])]))
                return 0;

            a = a->child[Map(s[id])];

            ++id;
        }

        return 0;
    }
} f, g;

int n, m;
string s[N];

void Read()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        cin >> s[i];
}

void Solve()
{
    sort(s + 1, s + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        string p = s[i];
        reverse(p.begin(), p.end());

        f.Add(p, i);

        g.Add(s[i], i);
    }

    for (int i = 1; i <= m; ++i)
    {
        string p, q;
        cin >> p >> q;

        pair<int, int> pos = g.Get(p);

        // cout << pos.first << " " << pos.second << "\n";

        reverse(q.begin(), q.end());

        cout << f.Cal(q, pos.first, pos.second) << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << endl;
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
1
3
1 0
1 1 2
0 3 4
*/