#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <numeric>

const int M = 500005;

char S[M];
int n, q;

struct SegmentTree {
    int sum;
    SegmentTree *ls, *rs;
    SegmentTree() : sum(0), ls(nullptr), rs(nullptr) {}
    SegmentTree(int sum, SegmentTree *ls, SegmentTree *rs) : sum(sum), ls(ls), rs(rs) {}
};

int safe_sum(const SegmentTree *p) {
    return p ? p->sum : 0;
}
SegmentTree *safe_ls(const SegmentTree *p) {
    return p ? p->ls : nullptr;
}
SegmentTree *safe_rs(const SegmentTree *p) {
    return p ? p->rs : nullptr;
}

SegmentTree *insert(SegmentTree *p, int l, int r, int a) {
    if (l == r) {
        return new SegmentTree(safe_sum(p) + 1, nullptr, nullptr);
    }
    int mid = (l + r) >> 1;
    if (a <= mid) {
        return new SegmentTree(safe_sum(p) + 1, insert(safe_ls(p), l, mid, a), safe_rs(p));
    } else {
        return new SegmentTree(safe_sum(p) + 1, safe_ls(p), insert(safe_rs(p), mid + 1, r, a));
    }
}

SegmentTree *merge(SegmentTree *p, SegmentTree *q) {
    if (!p || !q) {
        return p ? p : q;
    }
    return new SegmentTree(p->sum + q->sum, merge(p->ls, q->ls), merge(p->rs, q->rs));
}

int kth(SegmentTree *p, int l, int r, int k) {
    assert(k > 0 && k <= safe_sum(p));
    assert(l <= r);

    while (l < r) {
        int mid = (l + r) >> 1;
        if (k <= safe_sum(p->ls)) {
            r = mid;
            p = p->ls;
        } else {
            k -= safe_sum(p->ls);
            l = mid + 1;
            p = p->rs;
        }
    }
    return l;
}

template<size_t SIGMA, size_t M> struct SuffixAutomaton {
    int trans[2 * M][SIGMA]{};
    int mxlen[2 * M]{}, slink[2 * M]{};
    int ch[2 * M][SIGMA]{}, position[2 * M]{}, dfn[2 * M]{}, node[2 * M]{};
    long long sum[2 * M]{};
    SegmentTree *tr[2 * M]{};
    int tot, dfs_clock{};
    int n{};
    SuffixAutomaton() : tot(1) {
        slink[0] = -1;
        memset(ch[0], -1, sizeof ch[0]);
        memset(trans[0], -1, sizeof trans[0]);
    }
    int extend(int p, int c) {
        int q = tot++;
        mxlen[q] = mxlen[p] + 1;
        memset(trans[q], -1, sizeof trans[q]);
        memset(ch[q], -1, sizeof ch[q]);
        while (p != -1 && trans[p][c] == -1) {
            trans[p][c] = q;
            p = slink[p];
        }
        if (p == -1) {
            slink[q] = 0;
        } else {
            int r = trans[p][c];
            if (mxlen[r] == mxlen[p] + 1) {
                slink[q] = r;
            } else {
                int o = tot++;
                slink[o] = slink[r];
                mxlen[o] = mxlen[p] + 1;
                position[o] = position[r];
                memcpy(trans[o], trans[r], sizeof trans[o]);
                memset(ch[o], -1, sizeof ch[o]);
                while (trans[p][c] == r) {
                    trans[p][c] = o;
                    p = slink[p];
                }
                slink[q] = slink[r] = o;
            }
        }
        return q;
    }
    void dfs(int p) {
        // printf("%d\n", p);
        node[dfs_clock] = p;
        dfn[p] = dfs_clock++;
        for (int i = 0; i < SIGMA; ++i) {
            int q = ch[p][i];
            if (q == -1) {
                continue;
            }
            dfs(q);
            tr[p] = merge(tr[p], tr[q]);
        }
    }
    void build(char *S) {
        auto n = strlen(S);
        this->n = n;
        int last = 0;
        for (int i = 0; i < n; ++i) {
            last = extend(last, S[i] - 'a');
            // printf("%d\n", last);
            tr[last] = insert(tr[last], 0, n, i);
            position[last] = i;
        }
        // puts(S);
        // for (int i = 0; i < tot; ++i) {
        //     printf("%d %d %d %d\n", i, mxlen[i], position[i], slink[i]);
        // }
        for (int p = 1; p < tot; ++p) {
            int q = slink[p];
            ch[q][S[position[p] - mxlen[q]] - 'a'] = p;
        }
        dfs(0);
        for (int i = 1; i < tot; ++i) {
            int p = node[i];
            long long l = mxlen[slink[p]] + 1;
            long long r = mxlen[p];
            sum[i] = sum[i - 1] + safe_sum(tr[p]) * ((l + r) * (r - l + 1) >> 1);
            // printf("%d %d %lld %lld %lld\n", i, p, l, r, sum[i] - sum[i - 1]);
        }
    }
    int query(long long k) {
        int i = std::lower_bound(sum, sum + tot, k) - sum;
        assert(i != tot && i != 0);
        k -= sum[i - 1];
        int p = node[i];
        // printf("%d %lld\n", p, k);
        long long l = mxlen[slink[p]];
        long long r = mxlen[p];
        long long res = -1;
        auto f = [=](long long x) {
            return (x - mxlen[slink[p]]) * (x + mxlen[slink[p]] + 1) * tr[p]->sum >> 1;
        };
        while (l <= r) {
            long long mid = (l + r) >> 1;
            if (f(mid) < k) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        assert(res != -1);
        k -= f(res);
        // printf("%d %lld %lld %lld\n", p, k, res, tr[p]->sum - (k - 1) / (res + 1));
        // printf("%d\n", kth(tr[p], 0, n, tr[p]->sum - (k - 1) / (res + 1)));
        return kth(tr[p], 0, n, tr[p]->sum - (k - 1) / (res + 1)) - (k - 1) % (res + 1);
    }
};

SuffixAutomaton<26, M> sa;

int main() {
    scanf("%s%d", S, &q);
    n = (int) strlen(S);
    std::reverse(S, S + n);
    sa.build(S);
    for (int i = 0; i < q; ++i) {
        long long k;
        scanf("%lld", &k);
        printf("%d\n", n - sa.query(k));
    }
    return 0;
}