ksir

#include <bits/stdc++.h>
#define NMAX 200005
#define MAXLG 24
using namespace std;
ifstream fin("ksir.in");
ofstream fout("ksir.out");

long long n, i, j, q, lga, x;
long long DP[MAXLG][NMAX];
long long pozitie[NMAX], suma[NMAX], lung[NMAX];

string str;
struct elem
{
    long long nr1, nr2, ind;
}l[NMAX];
bool comp(const elem &a,const elem &b)
{
    if(a.nr1==b.nr1)
        return a.nr2<b.nr2;
    return a.nr1<b.nr1;
}
int main()
{

    fin>>str;
    n=str.size();
    for(int i=0;i<n;i++)
        DP[0][i]=str[i];
    for(lga=1;(1<<lga)<n;lga++)
    {
        for(j=0;j<n;j++)
        {
            l[j].ind=j;
            l[j].nr1=DP[lga-1][j];
            if(j+(1<<(lga-1))<n)
                l[j].nr2=DP[lga-1][j+(1<<(lga-1))];
            else l[j].nr2=-1;
        }
        sort(l,l+n,comp);
        for(j=0;j<n;j++)
            if(j && l[j].nr1==l[j-1].nr1 && l[j].nr2==l[j-1].nr2)
                DP[lga][l[j].ind]=DP[lga][l[j-1].ind];
            else DP[lga][l[j].ind]=j;
    }
    lga--;
    for(int i=0;i<n;i++)
        pozitie[DP[lga][i]]=i;
    int k=0;
    vector<int>rang(n+5,0);
    for(int i=0;i<n;i++)
       rang[pozitie[i]]=i;
    lung[0]=0;
    for(int i=0; i<n; i++, k ? k-- : 0)
    {
        if(rang[i]==n-1)
        {
            k=0;
            continue;
        }
        int j=pozitie[rang[i]+1];
        while(i+k<n && j+k<n && str[i+k]==str[j+k])
            k++;
        lung[rang[i]+1]=k;
    }
    suma[0]=n-pozitie[0];
    for(i=1;i<n;i++)
        suma[i]=suma[i-1]+(n-pozitie[i]-lung[i]);
    fin>>q;
    while(q--)
    {
        fin>>x;
        int lg=lower_bound(suma,suma+n,x)-suma;
        for(j=0,i=pozitie[lg];j<x-suma[lg-1]+lung[lg];i++,j++)
            fout<<str[i];
        fout<<'\n';
    }
    return 0;
}