首先，显然答案等于 \([1,r]\) 中符合条件的子串个数减去 \([1,l-1]\) 中符合条件的子串个数减去跨 \(l-1,l\) 的子串个数。前面两部分的处理是容易的，直接建出 ACAM 然后每加入一个字符就在上面条转移边即可。
考虑怎么处理跨中间的贡献。相当于我们要找 \([1,l-1]\) 的一段后缀与 \([l,r]\) 一段前缀拼起来得到某个 \(s_i\)。考虑再建出 \(s_i\) 反串的 ACAM 并定位出 \([l,r]\) 在反串 ACAM 上的节点，具体方法是，先从后到前扫一遍处理出每个后缀对应的反串在反 ACAM 上的节点，然后在反 ACAM 树上倍增直到对应节点的深度 \(\le r-l+1\)，我们设 \([1,l-1]\) 在正 ACAM 上对应的节点为 \(A\)，在 \([l,r]\) 在反 ACAM 上对应的节点为 \(B\)，那么我们相当于要求出有多少对 \((x,y)\) 满足 \(x\) 在正 fail 树上是 \(A\) 的祖先，\(y\) 在反 fail 树上是 \(B\) 的祖先，且 \(x,y\) 能拼成某个 \(s_i\)，离线 BIT 即可。
记 \(S=\sum|s_i|,T=|t|\)，时间复杂度 \(O(S\log S+T)\)。
const int MAXN=5e5;
const int MAXM=5e6;
const int MAXL=1e6;
const int LOG_N=20;
int n,m,qu;char t[MAXM+5],buf[MAXL+5];string s[MAXN+5];
struct ACAM{
int ch[MAXL+5][26],ncnt,cnt[MAXL+5],fail[MAXL+5],dep[MAXL+5];
void insert(string str){
int cur=0;
for(int i=0;i<str.size();i++){
if(!ch[cur][str[i]-'a'])ch[cur][str[i]-'a']=++ncnt,dep[ncnt]=i+1;
cur=ch[cur][str[i]-'a'];
}cnt[cur]++;
}
int hd[MAXL+5],to[MAXL+5],nxt[MAXL+5],ec;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
void getfail(){
queue<int>q;
for(int i=0;i<26;i++)if(ch[0][i])q.push(ch[0][i]);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<26;i++){
if(ch[x][i])fail[ch[x][i]]=ch[fail[x]][i],q.push(ch[x][i]);
else ch[x][i]=ch[fail[x]][i];
}
}
for(int i=1;i<=ncnt;i++)adde(fail[i],i);
}
}S,rv;
int sumc[MAXL+5],nd_pre[MAXM+5],nd_suf[MAXM+5],fa[MAXL+5][LOG_N+2];
int dfn[MAXL+5],edt[MAXL+5],tim;
ll sum[MAXM+5],res[MAXN+5];
void dfs1(int x){
dfn[x]=++tim;
for(int e=S.hd[x];e;e=S.nxt[e]){
int y=S.to[e];sumc[y]=sumc[x]+S.cnt[y];
dfs1(y);
}edt[x]=tim;
}
vector<pii>qv[MAXL+5];vector<int>ins[MAXL+5];
struct fenwick{
ll t[MAXL+5];
void add(int x,int v){for(int i=x;i<=S.ncnt+1;i+=(i&(-i)))t[i]+=v;}
ll query(int x){ll ret=0;for(int i=x;i;i&=(i-1))ret+=t[i];return ret;}
}T;
void dfs2(int x){
for(int id:ins[x])T.add(dfn[id],1),T.add(edt[id]+1,-1);
for(pii p:qv[x])res[p.se]-=T.query(dfn[p.fi]);
for(int e=rv.hd[x];e;e=rv.nxt[e])dfs2(rv.to[e]);
for(int id:ins[x])T.add(dfn[id],-1),T.add(edt[id]+1,1);
}
int main(){
scanf("%d%d%s",&n,&qu,t+1);m=strlen(t+1);
for(int i=1;i<=n;i++){
scanf("%s",buf+1);int len=strlen(buf+1);
for(int j=1;j<=len;j++)s[i].pb(buf[j]);
S.insert(s[i]);reverse(s[i].begin(),s[i].end());
rv.insert(s[i]);reverse(s[i].begin(),s[i].end());
}S.getfail();rv.getfail();dfs1(0);
for(int i=1;i<=m;i++)nd_pre[i]=S.ch[nd_pre[i-1]][t[i]-'a'];
for(int i=m;i;i--)nd_suf[i]=rv.ch[nd_suf[i+1]][t[i]-'a'];
for(int i=1;i<=m;i++)sum[i]=sum[i-1]+sumc[nd_pre[i]];
// for(int i=1;i<=m;i++)printf("%lld%c",sum[i]," \n"[i==m]);
for(int i=1;i<=rv.ncnt;i++)fa[i][0]=rv.fail[i];
for(int i=1;i<=LOG_N;i++)for(int j=1;j<=rv.ncnt;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1;i<=qu;i++){
int l,r;scanf("%d%d",&l,&r);
res[i]=sum[r]-sum[l-1];
int A=nd_pre[l-1],B=nd_suf[l];
for(int j=LOG_N;~j;j--)if(rv.dep[fa[B][j]]>r-l+1)B=fa[B][j];
if(rv.dep[B]>r-l+1)B=fa[B][0];
// printf("! %d %d\n",A,B);
qv[B].pb(mp(A,i));
}
for(int i=1;i<=n;i++){
vector<int>bk(s[i].size()+2),fw(s[i].size()+2);
for(int j=1;j<=s[i].size();j++)fw[j]=S.ch[fw[j-1]][s[i][j-1]-'a'];
for(int j=s[i].size();j;j--)bk[j]=rv.ch[bk[j+1]][s[i][j-1]-'a'];
for(int j=1;j<s[i].size();j++)ins[bk[j+1]].pb(fw[j]);
}
dfs2(0);
for(int i=1;i<=qu;i++)printf("%lld%c",res[i]," \n"[i==qu]);
return 0;
}