#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+5,INF=0x7fffffff;
int root[N],ls[N<<5],rs[N<<5],va[N<<5],ndcnt;
inline void up(int now){va[now]=max(va[ls[now]],va[rs[now]]);}
int query(int now,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return va[now];
	int mid=(l+r)>>1,ret=0;
	if(ql<=mid&&ls[now]) ret=max(ret,query(ls[now],l,mid,ql,qr));
	if(qr>mid&&rs[now]) ret=max(ret,query(rs[now],mid+1,r,ql,qr));
	return ret;
}
int modify(int now,int l,int r,int qp)
{
	int tmp=++ndcnt;
	if(l==r)
	{
		va[tmp]=qp;
		return tmp;
	}
	int mid=(l+r)>>1;
	ls[tmp]=ls[now],rs[tmp]=rs[now];
	if(qp<=mid) ls[tmp]=modify(ls[tmp],l,mid,qp);
	else rs[tmp]=modify(rs[tmp],mid+1,r,qp);
	up(tmp);return tmp;
}
int merge(int now1,int now2,int l,int r)
{
	int tmp=++ndcnt,mid=(l+r)>>1;
	if(l==r)
	{
		va[tmp]=l;
		return tmp;
	}
	if(ls[now1])
	{
		if(ls[now2]) ls[tmp]=merge(ls[now1],ls[now2],l,mid);
		else ls[tmp]=ls[now1];
	}
	else ls[tmp]=ls[now2];
	if(rs[now1])
	{
		if(rs[now2]) rs[tmp]=merge(rs[now1],rs[now2],mid+1,r);
		else rs[tmp]=rs[now1];
	}
	else rs[tmp]=rs[now2];
	up(tmp);return tmp;
}
int edp[N];
struct SAM
{
	int son[N][26],link[N],len[N],ndc=1,las=1,in[N];
	void reset()
	{
		for(int i=1;i<=ndc;i++)
		{
			link[i]=len[i]=in[i]=0;
			for(int j=0;j<26;j++) son[i][j]=0;
		}
		ndc=las=1;
	}
	inline void SAM_ext(int c)
	{
		int now=++ndc,tmp=las;
		len[now]=len[las]+1,las=now;
		while(tmp&&!son[tmp][c]) son[tmp][c]=now,tmp=link[tmp];
		if(!tmp) link[now]=1,in[1]++;
		else
		{
			int p=tmp,q=son[tmp][c];
			if(len[p]+1==len[q]) link[now]=q,in[q]++;
			else
			{
				int tt=++ndc;
				len[tt]=len[p]+1,link[tt]=link[q],in[tt]=2;
				for(int i=0;i<26;i++) son[tt][i]=son[q][i];
				link[now]=tt,link[q]=tt;
				while(tmp&&son[tmp][c]==q) son[tmp][c]=tt,tmp=link[tmp];
			}
		}
	}
} S,T;
int que[N],h,t,mt[N],mn[N],n,le;
char s[N],tp[N];
inline void match(int l,int r)
{
	int i,now=1,tlen=0;
	for(i=1;i<=le;i++)
	{
		int c=tp[i]-'a';
		while(now)
		{
			int aim=S.son[now][c];
			if(!aim) now=S.link[now],tlen=S.len[now];
			else
			{
				int ret=query(root[aim],1,n,1,r);
				if(ret>=l)
				{
					now=aim;
					tlen=min(tlen+1,ret-l+1);
					break;
				}
				else now=S.link[now],tlen=S.len[now];
			}
		}
		if(!now) now=1;
		mt[i]=tlen;
	}
}
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	int q,i,j;
	for(i=1;i<=n;i++)
	{
		edp[S.ndc+1]=i;
		S.SAM_ext(s[i]-'a');
	}
	for(i=1;i<=S.ndc;i++) if(!S.in[i]) que[t++]=i;
	while(h<t)
	{
		int now=que[h++],fa=S.link[now];
		if(edp[now]) root[now]=modify(root[now],1,n,edp[now]);
		if(fa) root[fa]=merge(root[fa],root[now],1,n);
		if(!--S.in[fa]) que[t++]=fa;
	}
	scanf("%d",&q);
	for(i=1;i<=q;i++)
	{
		int l,r;
		scanf("%s%d%d",tp+1,&l,&r);
		le=strlen(tp+1);
		match(l,r);
		T.reset();h=t=0;
		for(j=1;j<=le;j++)
		{
			mn[T.ndc+1]=j;
			T.SAM_ext(tp[j]-'a');
			//printf("%d ",mt[j]);
		}
		//printf("\n");
		long long ans=0;
		for(j=1;j<=T.ndc;j++)
		{
			if(!mn[j]) mn[j]=INF;
			if(!T.in[j]) que[t++]=j;
		}
		while(h<t)
		{
			int now=que[h++],fa=T.link[now];
			if(fa) mn[fa]=min(mn[fa],mn[now]);
			if(!--T.in[fa]) que[t++]=fa;
		}
		for(j=1;j<=T.ndc;j++) ans+=max(T.len[j]-max(mt[mn[j]],T.len[T.link[j]]),0),mn[j]=0;
		printf("%lld\n",ans);
	}
	return 0;
}

54 分，#19 及之后全 wa，数据弄下来和题解对拍（第四篇），发现挂掉的那一次询问串的 $p$ 数组和题解有一个位置不同。

答案统计跟 $p$ 数组没关系，match 我和第一篇题解比对过应该也没有锅（？），SAM 已经换成 copy 的板子了，所以难道是线段树合并的锅？？？

我已经缩小了很大的范围了，希望有大佬能帮我完成最后一步，找出虫来 qwq