1#include <bits/stdc++.h>
 2#define PB push_back
 3#define fst first
 4#define sec second
 5#define lson l,m,rt<<1
 6#define rson m+1,r,rt<<1|1
 7#define ms(a,x) memset(a,x,sizeof(a))
 8typedef long long LL;
 9#define pi pair < int ,int >
10#define MP make_pair

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6#define MAXALP 26

 1struct state
 2{
 3    int len, link, nxt[MAXALP];
 4};
 5const int N =3E5+7;
 6state st[N*2];
 7int sz, last,rt;
 8char s[N];
 9int cnt[2*N],a[2*N];//for radix sort
10int sum[2*N]; //表示状态i到终态的路径数
11void sa_init()
12{
13    sz = 0;
14    last = rt = ++sz;
15    st[1].len = 0;
16    st[1].link=-1;
17    ms(st[1].nxt,-1);
18    ms(cnt,0);
19}

 1void sa_extend(int c)
 2{
 3    int cur = ++sz;
 4    st[cur].len = st[last].len + 1;
 5    memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
 6    int p;
 7    for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
 8        st[p].nxt[c] = cur;
 9    if (p == -1) {
10        st[cur].link = rt;
11    } else {
12        int q = st[p].nxt[c];
13        if (st[p].len + 1 == st[q].len) {
14            st[cur].link = q;
15        } else {
16            int clone = ++sz ;
17            st[clone].len = st[p].len + 1;
18            st[clone].link = st[q].link;
19            memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
20            for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
21                st[p].nxt[c] = clone;
22            st[q].link = st[cur].link = clone;
23        }
24    }
25    last = cur;
26}
27void query( int k) //思想类似可持久化线段树找第k大
28//因为我们注意到，对于某个状态的所有转移，转移是j后得到的状态的所有子串的字典序一定比转移是(j+1)后得到的状态的所有子串的字典序小。
29{
30    int now = rt;
31    while (k)
32    {
33    for ( int i = 0 ; i < 26 ; i++)//字典序从小到大寻找，找到的一定是字典序最小的。
34        if (st[now].nxt[i]!=-1)
35        {
36        if (sum[st[now].nxt[i]]>=k)
37        {
38            putchar(('a'+i));
39            k--;
40            now = st[now].nxt[i];
41            break;
42        }
43        else k-=sum[st[now].nxt[i]]; //类似权值线段树找第k大
44        }
45    }
46    putchar('\n');
47}

 1int main()
 2{
 3    #ifndef  ONLINE_JUDGE 
 4    freopen("./in.txt","r",stdin);
 5  #endif
 6    sa_init();
 7    ms(sum,0);
 8    scanf("%s",s+1);
 9    int len = strlen(s+1);
10    for ( int i = 1 ; i <= len ; i++)
11    {
12        sa_extend(s[i]-'a');
13    }
14    //  a simple radix sort
15    for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
16    for ( int i = 1 ; i <= len ; i++) cnt[i]+=cnt[i-1];
17    for (int i = 1 ; i <= sz  ;i++) a[cnt[st[i].len]--] = i;
18//  for ( int i = 1 ; i <= sz ; i++) printf("a:%d\n",a[i]);
19    //将len按照从大到小的顺序存入临时数组a，a[1]表示len最短的状态的标号
20    //
21    //
22    //从len最长的更新，就是按照拓扑序更新。
23    //正确性在于len越大的越靠近SAM上的终止态
24    for ( int i = sz ; i >=1 ; i--)
25    {
26        int num = 0 ;
27        for ( int j = 0 ; j < 26 ; j++) if (st[a[i]].nxt[j]!=-1)
28        num+=sum[st[a[i]].nxt[j]];

 1        sum[a[i]] = num + 1; //到终态的路径数，等于其能到达的状态到终态的路径数之和sum+该状态到终态的路径数1.
 2    }
 3//  for ( int i = 1 ; i <= sz ; i++) printf("sum:%d\n",sum[i]);
 4    int q;
 5    cin>>q;
 6    while (q--)
 7    {
 8        int x;
 9        scanf("%d",&x);
10        query(x);
11    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}