#include <algorithm>
#include <cassert>
#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;
}

answer.code: In member function ‘void SuffixAutomaton<SIGMA, M>::build(char*)’:
answer.code:123:18: error: there are no arguments to ‘strlen’ that depend on a template parameter, so a declaration of ‘strlen’ must be available [-fpermissive]
  123 |         auto n = strlen(S);
      |                  ^~~~~~
answer.code:123:18: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
answer.code: In lambda function:
answer.code:158:18: warning: implicit capture of ‘this’ via ‘[=]’ is deprecated in C++20 [-Wdeprecated]
  158 |         auto f = [=](long long x) {
      |                  ^
answer.code:158:18: note: add explicit ‘this’ or ‘*this’ capture
answer.code: In function ‘int main()’:
answer.code:182:15: error: ‘strlen’ was not declared in this scope
  182 |     n = (int) strlen(S);
      |               ^~~~~~
answer.code:5:1: note: ‘strlen’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
    4 | #include <numeric>
  +++ |+#include <cstring>
    5 | 
answer.code: In instantiation of ‘SuffixAutomaton<SIGMA, M>::SuffixAutomaton() [with long unsigned int SIGMA = 26; long unsigned int M = 500005]’:
answer.code:178:24:   required from here
answer.code:75:15: error: ‘memset’ was not declared in this scope
   75 |         memset(ch[0], -1, sizeof ch[0]);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:75:15: note: ‘memset’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
answer.code:76:15: error: ‘memset’ was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
   76 |         memset(trans[0], -1, sizeof trans[0]);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code: In instantiation of ‘void SuffixAutomaton<SIGMA, M>::build(char*) [with long unsigned int SIGMA = 26; long unsigned int M = 500005]’:
answer.code:184:13:   required from here
answer.code:123:24: error: ‘strlen’ was not declared in this scope
  123 |         auto n = strlen(S);
      |                  ~~~~~~^~~
answer.code:123:24: note: ‘strlen’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
answer.code:181:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  181 |     scanf("%s%d", S, &q);
      |     ~~~~~^~~~~~~~~~~~~~~
answer.code:187:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  187 |         scanf("%lld", &k);
      |         ~~~~~^~~~~~~~~~~~