强烈谴责qn^2可过

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 5e6 + 10;
const ull B = 233;
using ul2 = array<ull, 2>;

#define printf __builtin_printf
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define rd read()
ll read()
{
    ll ch = 0, res = 0;
    if (!isdigit(ch))
    {
        ch = getchar();
    }
    if (!isdigit(ch))
    {
        ch = getchar();
    }
    while (isdigit(ch))
    {
        res = res * 10 + ch - '0', ch = getchar();
    }
    return res;
}
void read(string &s)
{
    s = "";
    char ch = getchar();
    if (!isalpha(ch))
    {
        ch = getchar();
    }
    if (!isalpha(ch))
    {
        ch = getchar();
    }
    while (isalpha(ch))
    {
        s += ch;
        ch = getchar();
    }
}

int n, q, m;
ull pwb[N], hsh[N];
vector<pair<ull, int>> tb[27][27][27];

inline ull hah(const string &s)
{
    ull res = 0;
    for (char ch : s)
    {
        res = res * B + ch - 'a';
    }
    return res;
}
inline void insert(const string &s)
{
    // cerr << "insert: " << s << '\n';
    tb[s[0] - 'a'][s[1] - 'a'][s[2] - 'a'].emplace_back(hah(s), (int)s.size());
}
inline ull get(int l, int r)
{
    return hsh[r] - hsh[l - 1] * pwb[r - l + 1];
}

signed main()
{
#ifdef ONLINE_JUDGE
    freopen("replace.in", "r", stdin);
    freopen("replace.out", "w", stdout);
#endif

    for (int i = pwb[0] = 1; i < N; ++i)
    {
        pwb[i] = pwb[i - 1] * B;
    }
    n = rd, q = rd;
    for (int i = 1; i <= n; ++i)
    {
        string s, t;
        read(s), read(t);
        int l = 0, r = s.size() - 1;
        if (s == t)
        {
            continue;
        }
        while (s[l] == t[l])
        {
            ++l;
        }
        while (s[r] == t[r])
        {
            --r;
        }
        insert(s.substr(0, l) + "{" + s.substr(l, r - l + 1) + t.substr(l, r - l + 1) + "{" + s.substr(r + 1));
    }
    while (q--)
    {
        string s, t;
        read(s), read(t);
        int l = 0, r = s.size() - 1, res = 0;
        if (s.size() != t.size())
        {
            cout << "0\n";
            continue;
        }
        while (s[l] == t[l])
        {
            ++l;
        }
        while (s[r] == t[r])
        {
            --r;
        }
        string st = "$" + s.substr(0, l) + "{" + s.substr(l, r - l + 1) + t.substr(l, r - l + 1) + "{" + s.substr(r + 1);
        m = st.size() - 1;
        // cerr << "query: " << st << '\n';
        for (int i = 1; i <= m; ++i)
        {
            hsh[i] = hsh[i - 1] * B + st[i] - 'a';
        }
        for (int i = 1, j = 2, k = 3; k <= m; ++i, ++j, ++k)
        {
            for (auto &[hh, len] : tb[st[i] - 'a'][st[j] - 'a'][st[k] - 'a'])
            {
                if (hh == get(i, i + len - 1) && i + len - 1 <= m)
                {
                    ++res;
                }
            }
        }
        printf("%d\n", res);
    }

    return 0;
}