#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1e5+10, inf = 1000111222;

int to_build[max_n];

template<typename T>
struct segment_tree
{
    vector<pair<T,pii>> all[4*max_n];

    void build(int v,int l,int r)
    {
        if (l==r){
            all[v].clear();
            all[v].pb(mp(to_build[l],mp(-1,-1)));
            return;
        }
        int m=(l+r)/2;
        build(2*v,l,m);
        build(2*v+1,m+1,r);
        int p1=0,p2=0;
        all[v].clear();
        all[v].reserve(r-l+1);

        while (p1<len(all[2*v]) || p2<len(all[2*v+1])){
            if (p1==len(all[2*v]) || (p2!=len(all[2*v+1]) && all[2*v][p1]>all[2*v+1][p2])){
                all[v].pb(mp(all[2*v+1][p2].fir,mp(p1,p2)));
                p2++;
            }
            else{
                all[v].pb(mp(all[2*v][p1].fir,mp(p1,p2)));
                p1++;
            }
        }
    }

    int get_cnt_more_equal(int v,int l,int r,int tl,int tr,int pos)
    {
        if (pos==all[v].size()){
            return 0;
        }
        if (l>=tl && r<=tr){
            return len(all[v])-pos;
        }
        int m=(l+r)/2;
        if (tr<=m){
            return get_cnt_more_equal(2*v,l,m,tl,tr,all[v][pos].sec.fir);
        }
        else if (tl>m){
            return get_cnt_more_equal(2*v+1,m+1,r,tl,tr,all[v][pos].sec.sec);
        }
        else{
            return get_cnt_more_equal(2*v,l,m,tl,tr,all[v][pos].sec.fir) +
                     get_cnt_more_equal(2*v+1,m+1,r,tl,tr,all[v][pos].sec.sec);
        }
    }

    int get_cnt_more_equal(int l,int r,int x)
    {
        const int pos=lower_bound(all(all[1]),mp(x,mp(-2,-2)))-all[1].begin();
        return get_cnt_more_equal(1,0,len(all[1])-1,l,r,pos);
    }

    int get_cnt_in_range(int l,int r,int x1,int x2)
    {
        return get_cnt_more_equal(l,r,x1)-get_cnt_more_equal(l,r,x2+1);
    }
};

segment_tree<int> st_fast;

struct segment_tree_min
{
    int mn[2*max_n];
//    int naive_mn[max_n];
    void build(int v,int l,int r)
    {
        mn[v]=+inf;
        if (l==r){
//            naive_mn[l]=+inf;
            return;
        }
        int m=(l+r)/2;
        build(v+1,l,m);
        build(v+2*(m-l+1),m+1,r);
    }


    void update(int v,int l,int r,int pos,int val)
    {
//        naive_mn[pos]=val;
//        return;

        if (l==r){
            mn[v]=val;
            return;
        }
        int m=(l+r)/2;
        if (pos<=m){
            update(v+1,l,m,pos,val);
        }
        else{
            update(v+2*(m-l+1),m+1,r,pos,val);
        }
        mn[v]=min(mn[v+1],mn[v+2*(m-l+1)]);
    }

    int get_min(int v,int l,int r,int tl,int tr)
    {
//        return *min_element(naive_mn+tl,naive_mn+tr+1);

        if (l==tl&&r==tr){
            return mn[v];
        }
        int m=(l+r)/2;
        if (tr<=m){
            return get_min(v+1,l,m,tl,tr);
        }
        else if (tl>m){
            return get_min(v+2*(m-l+1),m+1,r,tl,tr);
        }
        else{
            return min(
                    get_min(v+1,l,m,tl,m),
                    get_min(v+2*(m-l+1),m+1,r,m+1,tr)
                    );
        }
    }
};

segment_tree_min st_fast_fast;

struct segment_tree_min_spusk
{
    pii mn[2*max_n];
    pii mx[2*max_n];
    void build(int v,int l,int r)
    {
        if (l==r){
            mn[v]=mp(to_build[l],l);
            mx[v]=mp(-to_build[l],l);
            return;
        }
        int m=(l+r)/2;
        build(v+1,l,m);
        build(v+2*(m-l+1),m+1,r);
        mn[v]=min(mn[v+1],mn[v+2*(m-l+1)]);
        mx[v]=max(mx[v+1],mx[v+2*(m-l+1)]);
    }

    pair<bool,int> find_last_smaller(int v,int l,int r,int tl,int tr,int x)
    {
        if (l==tl&&r==tr){
            if (mn[v].fir<x){
                while (l!=r){
                    int m=(l+r)/2;
                    if (mn[v+2*(m-l+1)].fir<x){
                        v=v+2*(m-l+1);
                        l=m+1;
                    }
                    else{
                        v=v+1;
                        r=m;
                    }
                }
                return mp(1,l);
            }
            else{
                return mp(false,-1);
            }
        }
        int m=(l+r)/2;
        if (tr<=m){
            return find_last_smaller(v+1,l,m,tl,tr,x);
        }
        else if (tl>m){
            return find_last_smaller(v+2*(m-l+1),m+1,r,tl,tr,x);
        }
        else{
            auto res=find_last_smaller(v+2*(m-l+1),m+1,r,m+1,tr,x);
            if (res.first){
                return res;
            }

            return find_last_smaller(v+1,l,m,tl,m,x);
        }
    }

    pair<bool,int> find_first_smaller(int v,int l,int r,int tl,int tr,int x)
    {
        LOG(l,r,mn[v].fir);
        if (l==tl&&r==tr){
            if (mn[v].fir<x){
                while (l!=r){
                    int m=(l+r)/2;
                    if (mn[v+1].fir<x){
                        v=v+1;
                        r=m;
                    }
                    else{
                        v=v+2*(m-l+1);
                        l=m+1;
                    }
                }
                return mp(1,l);
            }
            else{
                return mp(false,-1);
            }
        }
        int m=(l+r)/2;
        if (tr<=m){
            return find_first_smaller(v+1,l,m,tl,tr,x);
        }
        else if (tl>m){
            return find_first_smaller(v+2*(m-l+1),m+1,r,tl,tr,x);
        }
        else{
            auto res=find_first_smaller(v+1,l,m,tl,m,x);
            if (res.first){
                return res;
            }
            return find_first_smaller(v+2*(m-l+1),m+1,r,m+1,tr,x);
        }
    }
};

segment_tree_min_spusk st3;

const int max_log=18;

//int st[max_n][max_log];

int lg[max_n];

ll ans[max_n];

int tp[max_n];

int naive(string s)
{
    set<string> res;
    for (int i=0;i<len(s);i++){
        for (int j=i;j<len(s);j++){
            res.insert(s.substr(i,j-i+1));
        }
    }
    return len(res);
}

const bool gen=0;
const bool stress=0;

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    start_of_program:;

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i=2;i<max_n;i++){
        lg[i]=lg[i/2]+1;
    }

    string s;
    if (gen){
        const int n=rand()%int(1e5)+1;
        s="";
        for (int i=0;i<n;i++){
            s+=char('a'+rand()%10);
        }
        cerr<<"new test"<<"\n";
        cerr<<s<<"\n";
    }
    else{
        cin>>s;
    }
    int q,w;
    if (gen){
        q=1;
        w=rand()%len(s)+1;
        cerr<<q<<" "<<w<<"\n";
    }
    else{
        cin>>q>>w;
    }
    auto solve_all=[&]()
    {
        const int base=char('a'-1);
        s+=char(base);
        const int n=len(s);

        for (int i=0;i<n;i++){
            tp[i]=s[i]-base;
        }
        for (int i=0;i<max_log;i++){
            vector<pair<pii,int>> v;
            for (int j=0;j<n;j++){
                v.pb(mp(mp(tp[j],tp[(j+(1ll<<i))%n]),j));
            }
            sort(all(v));
            int last=0;
            for (int j=0;j<len(v);){
                tp[v[j].sec]=last;
                while (j+1<len(v) && v[j+1].fir==v[j].fir){
                    j++;
                    tp[v[j].sec]=last;
                }

                last++;
                j++;
            }
        }

        vector<pii> p(n);
        for (int i=0;i<n;i++){
            LOG(s.substr(i),tp[i]);
            p[i]=mp(tp[i],i);
        }
        sort(all(p));
        vector<int> v(n);
        for (int i=0;i<n;i++){
            v[i]=p[i].sec;
        }


        vector<int> pos(n+2,0);

        vector<int> lcp(n,0);
        for (int i=0;i<n;i++){
            pos[v[i]]=i;
        }
        int len=0;
        for (int i=0;i<n;i++){
            if (pos[i]==0){
                len=0;
                continue;
            }
            len=max(len-1,0);
            int id=v[pos[i]-1];
            while (i+len<n && id+len<n && s[i+len]==s[id+len]){
                len++;
            }
            lcp[pos[i]]=len;
        }

        DEBUG{
            for (int i=0;i<n;i++){
                cerr<<s.substr(v[i])<<" "<<lcp[i]<<"\n";
            }
        };

//        for (int i=0;i<n;i++){
//            to_build[i]=v[i];
//        }
//        st_fast.build(1,0,n-1);

        for (int i=0;i<n;i++){
            to_build[i]=lcp[i];
        }
        to_build[0]=+inf;
        st3.build(1,0,n-1);


//        for (int i=0;i<n;i++){
//            st[i][0]=lcp[i];
//        }
//        for (int j=1;j<max_log;j++){
//            for (int i=0;i+(1ll<<j)-1<n;i++){
//                st[i][j]=min(st[i][j-1],st[i+(1ll<<(j-1))][j-1]);
//            }
//        }
//
//        auto get_st_min=[&](int l,int r)
//        {
//            int my_lg=lg[r-l+1];
//            return min(st[l][my_lg],st[r-(1ll<<my_lg)+1][my_lg]);
//        };
//        auto get_lcp=[&](int pos_v_1,int pos_v_2)
//        {
//            assert(pos_v_1<pos_v_2);
//            return get_st_min(pos_v_1+1,pos_v_2);
//        };

        st_fast_fast.build(1,0,n-1);

        ll answer=0;
        auto any_have_prefix=[&](int l,int r,int want_l,int want_r)
        {
            const int length=want_r-want_l+1;
            const int my_pos_in_v=pos[want_l];
            int L=my_pos_in_v,R=my_pos_in_v;
            LOG("R before",R);
            {
                auto res=st3.find_last_smaller(1,0,n-1,0,L,length);
                if (res.fir){
                    L=res.sec;
                }
                else{
                    L=0;
                }
            }
            if (R!=n-1){
                auto res=st3.find_first_smaller(1,0,n-1,R+1,n-1,length);
                LOG(res.fir,res.sec);
                if (res.fir){
                    R=res.sec-1;
                }
                else{
                    R=n-1;
                }
            }
//            for (int i=max_log;i>=0;i--){
//                if (L-(1ll<<i)>=0 && get_lcp(L-(1ll<<i),my_pos_in_v)>=length){
//                    L-=(1ll<<i);
//                }
//            }
//            for (int i=max_log;i>=0;i--){
//                if (R+(1ll<<i)<n && get_lcp(my_pos_in_v,R+(1ll<<i))>=length){
//                    R+=(1ll<<i);
//                }
//            }
//            LOG("R after",R);
//            LOG(length);
//            LOG(n-1);
//            assert(R==my_pos_in_v || get_lcp(my_pos_in_v,R)>=length);
            return st_fast_fast.get_min(1,0,n-1,L,R)<=r;
//            return st_fast.get_cnt_in_range(L,R,l,r)>0;

//            for (int i=l;i<=r;i++){
//                if (s.substr(i,length)==s.substr(want_l,length)){
//                    return 1;
//                }
//            }
//            return 0;
        };
        auto push_to_subseg=[&](int L,int R)
        {
            LOG("push_to_subseg",L,R);
            int l=L,r=R;
            while (r-l>0){
                int m=(l+r+1)/2;
                /// [m;R]
                const int length=R-m+1;
                if (any_have_prefix(L,R-length,m,R)){
                    r=m-1;
                }
                else{
                    l=m;
                }
            }
            LOG("res of bin search",l);
            answer+=(l-L+1);
            LOG("new answer",answer);
            st_fast_fast.update(1,0,n-1,pos[R],R);
        };
        auto pop_from_subseg=[&](int L,int R)
        {
            st_fast_fast.update(1,0,n-1,pos[L],+inf);
            int l=L,r=R;
            while (r-l>0){
                int m=(l+r)/2;
                /// [L;m]
                const int length=m-L+1;
                if (any_have_prefix(L+1,R-length+1,L,m)){
                    l=m+1;
                }
                else{
                    r=m;
                }
            }
            answer-=(R-l+1);
        };

        if (w==1){
            for (int i=0;i<n;i++){
                ans[i]=1;
            }
        }
        else{
            answer=0;
            for (int i=0;i<w;i++){
                push_to_subseg(0,i);
            }
            ans[0]=answer;
            for (int i=1;i+w-1<n;i++){
                int L=i,R=i+w-1;
                L--;
                R--;

                pop_from_subseg(L,R);
                L++;

                R++;
                push_to_subseg(L,R);
                ans[i]=answer;
            }
        }

//        for (int i=0;i+w-1<n;i++){
//            vector<int> pos_in_v;
//            for (int j=0;j<w;j++){
//                pos_in_v.pb(pos[i+j]);
//            }
//            sort(all(pos_in_v));
//            for (int j=1;j<len(pos_in_v);j++){
//                ans[i]-=min(i+w-1-max(v[pos_in_v[j-1]],v[pos_in_v[j]])+1,get_lcp(pos_in_v[j-1],pos_in_v[j]));
//            }
//            ans[i]+=1ll*w*(w+1)/2;
//            LOG("answer for",s.substr(i,w),ans[i]);
//        }
        return;

//        int push=0;
//        ll value=0;
//        set<int> setik;
//        set<pair<int,pii>> to_remove_push;
//        int CURRENT_R;
//        auto add_pair_to_setik=[&](int pos_v_1,int pos_v_2)
//        {
//            LOG("add_pair_to_setik",s.substr(v[pos_v_1]),s.substr(v[pos_v_2]));
//            int lcp=get_lcp(pos_v_1,pos_v_2);
//            LOG(lcp);
//            if (max(v[pos_v_1],v[pos_v_2])+lcp-1>=CURRENT_R){
//                to_remove_push.insert(mp(max(v[pos_v_1],v[pos_v_2])+lcp-1,mp(pos_v_1,pos_v_2)));
//                push++;
//                value+=CURRENT_R-max(v[pos_v_1],v[pos_v_2])+1;
//                LOG("added to value",CURRENT_R-max(v[pos_v_1],v[pos_v_2])+1);
//            }
//            else{
//                value+=lcp;
//            }
//        };
//        auto remove_pair_from_setik=[&](int pos_v_1,int pos_v_2)
//        {
//            LOG("remove_pair_from_setik",s.substr(v[pos_v_1]),s.substr(v[pos_v_2]));
//            int lcp=get_lcp(pos_v_1,pos_v_2);
//            if (max(v[pos_v_1],v[pos_v_2])+lcp-1>=CURRENT_R){
//                to_remove_push.erase(mp(max(v[pos_v_1],v[pos_v_2])+lcp-1,mp(pos_v_1,pos_v_2)));
//                push--;
//                value-=CURRENT_R-max(v[pos_v_1],v[pos_v_2])+1;
//            }
//            else{
//                value-=lcp;
//            }
//        };
//
//        auto add_to_setik=[&](int id)
//        {
//            LOG("add_to_setik",s.substr(id));
//            int value_of_id=pos[id];
//            auto it=setik.insert(value_of_id).fir;
//            if (it!=setik.begin() && next(it)!=setik.end()){
//                remove_pair_from_setik(*prev(it),*next(it));
//            }
//            if (it!=setik.begin()){
//                add_pair_to_setik(*prev(it),*it);
//            }
//            if (next(it)!=setik.end()){
//                add_pair_to_setik(*it,*next(it));
//            }
//        };
//        auto remove_from_setik=[&](int id)
//        {
//            LOG("remove_from_setik",s.substr(id));
//            int value_of_id=pos[id];
//            auto it=setik.find(value_of_id);
//            if (it!=setik.begin()){
//                remove_pair_from_setik(*prev(it),*it);
//            }
//            if (next(it)!=setik.end()){
//                remove_pair_from_setik(*it,*next(it));
//            }
//            if (it!=setik.begin() && next(it)!=setik.end()){
//                add_pair_to_setik(*prev(it),*next(it));
//            }
//            setik.erase(value_of_id);
//        };
//        auto try_remove_push=[&](pii poses_v)
//        {
//            const int pos_v_1=poses_v.fir;
//            const int pos_v_2=poses_v.sec;
//            int lcp=get_lcp(pos_v_1,pos_v_2);
//            assert(max(v[pos_v_1],v[pos_v_2])+lcp-1==CURRENT_R);
//            {
//                push--;
//                value-=CURRENT_R-max(v[pos_v_1],v[pos_v_2])+1;
//            }
//            {
//                value+=lcp;
//            }
//        };
//
//        CURRENT_R=w-1;
//        for (int i=0;i<w;i++){
//            add_to_setik(i);
//        }
//        ans[0]=-value+1ll*w*(w+1)/2;
//        LOG("found zero answer",ans[0]);
//        while (!to_remove_push.empty() && to_remove_push.begin()->fir==w-1){
//            try_remove_push(to_remove_push.begin()->sec);
//            to_remove_push.erase(to_remove_push.begin());
//        }
//
//
//        for (int i=1;i+w-1<n;i++){
//            value+=push;
//            CURRENT_R=i+w-1;
//            remove_from_setik(i-1);
//            add_to_setik(i+w-1);
//            ans[i]=-value+1ll*w*(w+1)/2;
//            LOG("found",i,"answer",ans[i]);
//            while (!to_remove_push.empty() && to_remove_push.begin()->fir==i+w-1){
//                try_remove_push(to_remove_push.begin()->sec);
//                to_remove_push.erase(to_remove_push.begin());
//            }
//        }
    };
    for (int i=0;i<len(s)+3;i++){
        ans[i]=0;
    }
    solve_all();
//    for (int i=0;i+w-1<len(s)-1;i++){
//        ll smart_ans=ans[i];
//        ll naive_ans=naive(s.substr(i,w));
//        if (smart_ans!=naive_ans){
//            LOG(i,smart_ans,naive_ans);
//            cerr<<"VERY_BAD"<<"\n";
//            exit(123);
//        }
//    }
    for (int i=0;i<q;i++){
        int pos;
        if (gen){
            pos=1;
            cerr<<pos<<"\n";
        }
        else{
            cin>>pos;
        }
        pos--;

        cout<<ans[pos]<<"\n";
    }

    if (stress){
        goto start_of_program;
    }
}