[NOI2018]你的名字

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=1e6+5;
struct p{
	int l,r;
}s[MAX<<5];
int n,Q,tot;
int rt[MAX],L_max[MAX],pos[MAX];
char a[MAX];
void change(int l,int r,int &k,int x)
{
	if(!k) k=++tot;
	if(l==r) return;
	if(x<=mid) change(l,mid,tl,x);
	else change(mid+1,r,tr,x);
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	int k=++tot;
	return tl=merge(s[x].l,s[y].l),tr=merge(s[x].r,s[y].r),k;
}
bool ask(int l,int r,int k,int L,int R)
{
	if(R<l||r<L||!k||L>R) return 0;
	if(l>=L&&r<=R) return 1;
	return (ask(l,mid,tl,L,R)|ask(mid+1,r,tr,L,R));
}
struct SAM{
	int l,r,L;
	int len[MAX],fa[MAX],id[MAX],tax[MAX];
	int son[MAX][26];
	SAM() {l=r=1;}
	void ins(int x,int id,bool fl=0)
	{
		int tt=r;
		len[r=++l]=++L;
		if(!fl) change(1,n,rt[r],id);
		else pos[r]=id;
		for(;tt&&!son[tt][x];tt=fa[tt])
		  son[tt][x]=r;
		if(!tt) return void(fa[r]=1);
		int qwq=son[tt][x];
		if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
		len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
		for(int i=0;i<26;++i)
		  son[l][i]=son[qwq][i];
		for(int i=tt;son[i][x]==qwq;i=fa[i])
		  son[i][x]=l;
	}
	void Solve(int _n,int l,int r)
	{
		for(int i=1,x=1,_L=0;i<=_n;++i)
		  {
		  	if(son[x][a[i]-'a']&&ask(1,n,rt[son[x][a[i]-'a']],l+_L,r)) x=son[x][a[i]-'a'],++_L;
		  	else
		  	{
		  		while(x&&(!son[x][a[i]-'a']||!ask(1,n,rt[son[x][a[i]-'a']],l+_L,r)))
				{
					if(!_L) {x=0;break;}
				  	--_L;
				  	if(_L==len[fa[x]]) x=fa[x];
				}
		  		if(!x) x=1,_L=0;
		  		else ++_L,x=son[x][a[i]-'a'];
			}
			L_max[i]=_L;
		  }
	}
	void mem()
	{
		for(int i=1;i<=l;++i)
		  {
		  	tax[i]=pos[i]=0;
		  	for(int j=0;j<26;++j)
			  son[i][j]=0;
		  }
		l=r=1,L=0;
	}
	void Init(int _n)
	{
		for(int i=1;i<=l;++i)
		  ++tax[len[i]];
		for(int i=1;i<=_n;++i)
		  tax[i]+=tax[i-1];
		for(int i=l;i>=1;--i)
		  id[tax[len[i]]--]=i;
	}
	void GET_MERGE()
	{
		for(int i=l;i>=1;--i)
		  if(fa[id[i]]) rt[fa[id[i]]]=merge(rt[fa[id[i]]],rt[id[i]]);
	}
	void GET_POS()
	{
		for(int i=l;i>=1;--i)
		  pos[fa[id[i]]]=max(pos[fa[id[i]]],pos[id[i]]);
	}
}_S,__S;
LL GET_ANS(int _n)
{
	LL ans=0;
	__S.Init(_n),__S.GET_POS();
	for(int i=2;i<=__S.l;++i)
	  ans+=__S.len[i]-min(__S.len[i],max(__S.len[__S.fa[i]],L_max[pos[i]]));
	return ans;
}
int main()
{
	scanf("%s",a+1),n=strlen(a+1);
	for(int i=1;i<=n;++i)
	  _S.ins(a[i]-'a',i);
	_S.Init(n),_S.GET_MERGE(),scanf("%d",&Q);
	for(int i=1,_n,l,r;i<=Q;++i)
	  {
	  	scanf("%s%d%d",a+1,&l,&r);
		__S.mem(),_n=strlen(a+1);
		for(int j=1;j<=_n;++j)
		  __S.ins(a[j]-'a',j,1);
		_S.Solve(_n,l,r),printf("%lld\n",GET_ANS(_n));
	  }
	return 0;
}