1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define ll long long

 5 int V,last,ans,a[N<<1],sz[N<<1],mi[N<<1],id[N<<1],len[N<<1],fa[N<<1],ch[N<<1][31];

 6 ll k,mod,l[N<<1],sum[N<<1];

 7 char s[N];

 8 void add(int c){

 9     int p=last,np=last=++V;

10     len[np]=len[p]+1;

11     sz[np]=1;

12     for(;(p)&&(!ch[p][c]);p=fa[p])ch[p][c]=V;

13     if (!p)fa[np]=1;

14     else{

15         int q=ch[p][c];

16         if (len[q]==len[p]+1)fa[np]=q;

17         else{

18             int nq=++V;

19             len[nq]=len[p]+1;

20             memcpy(ch[nq],ch[q],sizeof(ch[q]));

21             fa[nq]=fa[q];

22             fa[np]=fa[q]=nq;

23             for(;(p)&&(ch[p][c]==q);p=fa[p])ch[p][c]=nq;

24         }

25     }

26 }

27 void dfs(int k){

28     a[++a[0]]=k;

29     for(int i=0;i<26;i++)

30         if (ch[k][i])dfs(ch[k][i]);

31 }

32 int main(){

33     int t;

34     scanf("%s%d",s,&t);

35     V=last=1;

36     int n=strlen(s);

37     for(int i=n-1;i>=0;i--)add(s[i]-'a');

38     for(int i=1;i<=V;i++)a[len[i]]++;

39     for(int i=1;i<=n;i++)a[i]+=a[i-1];

40     for(int i=1;i<=V;i++)id[a[len[i]]--]=i;

41     for(int i=1,j=n;i<=V;i++)

42         if (sz[i])mi[i]=--j;

43     memset(a,0,sizeof(a));

44     for(int i=V;i;i--){

45         sz[fa[id[i]]]+=sz[id[i]];

46         mi[fa[id[i]]]=mi[id[i]];

47     }

48     for(int i=V;i;i--)l[i]=(len[fa[i]]+len[i]+1LL)*(len[i]-len[fa[i]])/2*sz[i];

49     memset(ch,0,sizeof(ch));

50     for(int i=1;i<=V;i++)ch[fa[i]][s[mi[i]+len[fa[i]]]-'a']=i;

51     dfs(1);

52     for(int i=1;i<=V;i++)sum[i]=sum[i-1]+l[a[i]];

53     while (t--){

54         scanf("%lld%lld",&k,&mod);

55         k=k*ans%mod+1;

56         int p=lower_bound(sum+1,sum+V+1,k)-sum;

57         k-=sum[p-1];

58         p=a[p];

59         int x=len[fa[p]]+1,y=len[p];

60         while (x<y){

61             int mid=(x+y>>1);

62             if ((mid+len[fa[p]]+1LL)*(mid-len[fa[p]])/2*sz[p]>=k)y=mid;

63             else x=mid+1;

64         }

65         k-=(x+len[fa[p]])*(x-1LL-len[fa[p]])/2*sz[p];

66         printf("%c\n",s[(k-1)%x+mi[p]]);

67         ans+=s[(k-1)%x+mi[p]];

68     }

69 }