#include<bits/stdc++.h> #define N 2000011 #define LL long long #define Mid (l+r>>1) #define Max(a,b) (a>b?a:b) #define Min(a,b) (a<b?a:b) using namespace std; int ls[N*20],rs[N*20],sz[N*20],size=1,n,last=1,siz; char S[N]; inline void ins(int &now,int l,int r,int pos){ if (!now) now=++siz; if (l==r) return (void) (sz[now]++); if (pos<=Mid) ins(ls[now],l,Mid,pos); else ins(rs[now],Mid+1,r,pos); sz[now]=sz[ls[now]]+sz[rs[now]]; } int merge(int x,int y,int l,int r){ if (!x||!y) return x+y; int o=++siz; if (l==r) sz[o]=sz[x]+sz[y]; else { ls[o]=merge(ls[x],ls[y],l,Mid); rs[o]=merge(rs[x],rs[y],Mid+1,r); sz[o]=sz[ls[o]]+sz[rs[o]]; } return o; } int query(int u,int l,int r,int pos){ if (!sz[u]) return 0; if (l==r) return l; if (pos<=Mid) return query(ls[u],l,Mid,pos); int ran=query(rs[u],Mid+1,r,pos); return ran?ran:query(ls[u],l,Mid,pos); } vector<int> g[N],v; int fa[N],ch[N][26],mx[N],mi[N],rt[N],dep[N],vis[N]; void add(){ for (int i=2;i<=size;i++) g[fa[i]].push_back(i); } void dfs(int x){ for(int i=g[x].size()-1;~i;i--) { dfs(g[x][i]),rt[x]=merge(rt[x],rt[g[x][i]],1,n); mx[x]=Max(mx[x],mx[g[x][i]]); mi[x]=Min(mi[x],mi[g[x][i]]); } } void pre(int x,int ff,int pos){ int np=++size; dep[np]=dep[last]+1; if (ff) v.push_back(np); else { ins(rt[np],1,n,pos); mx[np]=mi[np]=pos; } for (;last&&!ch[last][x];last=fa[last]) ch[last][x]=np; if (!last) return (void) (fa[np]=1,last=np); int q=ch[last][x]; if (dep[last]+1==dep[q]) return (void) (fa[np]=q,last=np); int nq=++size; dep[nq]=dep[last]+1; // assert(dep[]) fa[nq]=fa[q]; fa[np]=fa[q]=nq; if (ff) rt[nq]=rt[q],mx[nq]=mx[q],mi[nq]=mi[q]; memcpy(ch[nq],ch[q],sizeof ch[q]); for (;last&&ch[last][x]==q;last=fa[last]) ch[last][x]=nq; last=np; // cerr<<"kk"<<size<<endl; } LL calc(char *s,int l,int r){ last=1; v.clear(); LL len=strlen(s),ans=0,all=0; for (int i=0;i<len;i++) pre(s[i]-'a',1,0); // cerr<<size<<endl; for (int i=0;i<v.size();i++) { for (int p=v[i];p>1;p=fa[p]) { if (vis[p]) break; all+=dep[p]-dep[fa[p]],vis[p]=1; if (rt[p]) { if ((l==1&&r==n)) { ans+=dep[p]-dep[fa[p]]; continue;} if (mx[p]<l||mi[p]>r) continue; int mxlen= (mx[p]<=r)?mx[p]-l+1:query(rt[p],1,n,r)-l+1; if (mxlen>dep[fa[p]]) ans+=Min(dep[p],mxlen)-dep[fa[p]]; } } } for(int i=0;i<v.size();i++){ for(int p=v[i];p>1;p=fa[p]){ if(!vis[p]) break; vis[p] = 0; } } // cerr<<all<<' '<<ans<<endl; return all - ans; } int q,l,r,pos[N]; LL ans; signed main () { freopen("name.in","r",stdin); freopen("name.out","w",stdout); scanf("%s",S+1); n=strlen(S+1); for(int i=1;i<=n;i++) pre(S[i]-'a',0,i); add(),dfs(1); scanf("%d",&q); while (q--) { scanf("%s",S+1); scanf("%d%d",&l,&r); printf("%lld ",calc(S+1,l,r)); } return 0; }