const int P = 239017;
const int HMOD = (int)1e9 + 87;

int mul(int a, int b)
{
    return ((ll)a * b) % HMOD;
}

void solve (char* s, int k, char** a, int q, query_t* qs, ll* ans)
{
    for (int i = 0; i < q; i++)
        ans[i] = 0;
    int n = strlen(s);
    vi p(n + 1);
    p[0] = 1;
    for (int i = 1; i <= n; ++i)
        p[i] = mul(p[i - 1], P);
    vi h(n);
    h[0] = s[0];
    vi sz(k);
    for (int i = 0; i < k; ++i)
        sz[i] = strlen(a[i]);
    for (int i = 1; i < n; ++i)
    {
        h[i] = mul(h[i - 1], P) + s[i];
        if (h[i] >= HMOD)
            h[i] -= HMOD;
    }
    int cntlen = 0;
    set<int> lns;
    for (int i = 0; i < k; ++i)
    {
        lns.insert(sz[i]);
    }
    cntlen = lns.size();
    vi id2len;
    id2len.reserve(cntlen);
    for (int x : lns)
        id2len.inb(x);
    //precalc hashes
    unordered_set<int> cnt[cntlen];
    for (int i = 0; i < k; ++i)
    {
        int clen = sz[i];
        int id = lower_bound(all(id2len), clen) - id2len.begin();
        int ch = 0;
        for (int j = 0; j < clen; ++j)
        {
            ch = mul(ch, P) + a[i][j];
            if (ch >= HMOD)
                ch -= HMOD;
        }
        cnt[id].insert(ch);
    }
    int pr[cntlen][n];
    //precalced pr sums
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < cntlen; ++j)
        {
            if (i)
                pr[j][i] = pr[j][i - 1];
            else
                pr[j][i] = 0;
            if (id2len[j] + i > n)
                continue;
            int chash = h[i + id2len[j] - 1];
            if (i)
                chash -= mul(h[i - 1], p[id2len[j]]);
            if (chash < 0)
                chash += HMOD;
            if (cnt[j].find(chash) != cnt[j].end())
            {
                pr[j][i]++;
            }
        }
    }
    //zapros odin otvet drugoy
    for (int it = 0; it < q; ++it)
    {
        int l = qs[it].l - 1;
        int r = qs[it].r - 1;
        for (int i = 0; i < cntlen; ++i)
        {
            if (id2len[i] > r - l + 1)
                continue;
            ans[it] += pr[i][r - id2len[i] + 1];
            if (l)
                ans[it] -= pr[i][l - 1];
        }
    }
}