题目大意：
给定一个母串和若干个询问串，求每个询问串有多少个本质不同的子串没有在母串中出现过。
思路：
ION2017的串我们称为S串，ION2018的串我们称为T串。
先考虑68pts怎么去做。
考虑T串有多少个子串未在S串中出现过，于是将S建立SAM，然后将T丢进S的SAM里跑子串匹配，这样我们可以得到T的每一个结束位置的最大匹配长度，所有长度大于这个长度的子串都是符合要求的子串。
上述方法对于出现位置不同的子串会算重，于是考虑对T串也建立SAM来去重，依旧考虑上面的思想，我们对T的SAM的每一个状态都算出在S中的最大匹配长度即可。
接下来考虑如何解决l,r任意的情况，我们同样考虑去对T建SAM之后在SAM的每一个状态上面计算出匹配出的最长长度，只是匹配的位置有了限制，要求的匹配的子串整个在[l,r]之间，判断长度为len的子串是否出现，要求这个节点right集合有在[l+len-1,r]的元素，于是我们只需要记录下每个节点的right集合是什么，这个用支持可持久化的线段树合并维护即可。跳到一个新的节点如果不匹配，那么我们可以一个单位一个单位地跳长度来判断。
由于每次匹配长度至多会增加1，所以这样暴力跳长度的做法复杂度也是线性的。
/*=======================================
* Author : ylsoi
* Time : 2019.2.19
* Problem : luogu4770
* E-mail : ylsoi@foxmail.com
* ====================================*/
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define debug(x) cout<<#x<<"="<<x<<" "
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define mid ((l+r)>>1)
typedef long long ll;
using namespace std;
void File(){
freopen("luogu4770.in","r",stdin);
freopen("luogu4770.out","w",stdout);
}
template<typename T>void read(T &_){
_=0; T f=1; char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())_=(_<<1)+(_<<3)+(c^'0');
_*=f;
}
const int maxn=5e5+10;
struct Suffix_Automaton{
int ch[maxn<<1][26],fa[maxn<<1],len[maxn<<1],pos[maxn<<1];
int cnt,last;
Suffix_Automaton(){cnt=last=1;}
void insert(int x,int y){
int p=last,np=last=++cnt;
len[np]=len[p]+1;
pos[np]=y;
while(p && !ch[p][x])ch[p][x]=np,p=fa[p];
if(!p)fa[np]=1;
else{
int q=ch[p][x];
if(len[q]==len[p]+1)fa[np]=q;
else{
int nq=++cnt;
memcpy(ch[nq],ch[q],sizeof(ch[nq]));
len[nq]=len[p]+1,fa[nq]=fa[q];
fa[q]=fa[np]=nq;
pos[nq]=y;
while(p && ch[p][x]==q)ch[p][x]=nq,p=fa[p];
}
}
}
void clear(){
REP(i,1,cnt){
fa[i]=0;
len[i]=0;
pos[i]=0;
memset(ch[i],0,sizeof(ch[i]));
}
cnt=last=1;
}
}S,T;
int n,m,q,lim[maxn];
char s[maxn],t[maxn];
int root[maxn<<1],ch[maxn<<6][2],sum[maxn<<6],cnt;
void update(int &o,int l,int r,int x){
if(!o)o=++cnt;
++sum[o];
if(l==r)return;
if(x<=mid)update(ch[o][0],l,mid,x);
else update(ch[o][1],mid+1,r,x);
}
int merge(int x,int y){
if(!x || !y)return x+y;
int now=++cnt;
sum[now]=sum[x]+sum[y];
ch[now][0]=merge(ch[x][0],ch[y][0]);
ch[now][1]=merge(ch[x][1],ch[y][1]);
return now;
}
int query(int o,int l,int r,int L,int R){
if(l>r || !o)return 0;
if(L<=l && r<=R)return sum[o];
else{
int ret=0;
if(L<=mid)ret+=query(ch[o][0],l,mid,L,R);
if(R>=mid+1)ret+=query(ch[o][1],mid+1,r,L,R);
return ret;
}
}
int tax[maxn<<1],lis[maxn<<1];
void build_parent_tree(){
REP(i,1,S.cnt)if(S.pos[i])
update(root[i],1,n,S.pos[i]);
REP(i,1,n)tax[i]=0;
REP(i,1,S.cnt)++tax[S.len[i]];
REP(i,1,n)tax[i]+=tax[i-1];
REP(i,1,S.cnt)lis[tax[S.len[i]]--]=i;
DREP(i,S.cnt,1){
int u=lis[i],f=S.fa[u];
root[f]=merge(root[f],root[u]);
}
}
ll solve(int l,int r){
int o=1,now=0;
REP(i,1,m){
int x=t[i]-'a';
while(o!=1 && !S.ch[o][x])o=S.fa[o],now=S.len[o];
if(S.ch[o][x]){
o=S.ch[o][x],++now;
while(o!=1){
if(query(root[o],1,n,l+now-1,r))break;
if((--now)==S.len[S.fa[o]])o=S.fa[o];
}
}
lim[i]=now;
}
ll ret=0;
REP(i,1,T.cnt){
int p=T.pos[i],max_len=T.len[i];
if(lim[p]<=max_len)
ret+=max_len-max(T.len[T.fa[i]],lim[p]);
}
return ret;
}
int main(){
File();
scanf("%s",s+1);
n=strlen(s+1);
REP(i,1,n)S.insert(s[i]-'a',i);
build_parent_tree();
read(q);
int l,r;
REP(i,1,q){
scanf("%s",t+1);
m=strlen(t+1);
read(l),read(r);
REP(j,1,m)T.insert(t[j]-'a',j);
printf("%lld
",solve(l,r));
T.clear();
}
return 0;
}