思路就是 ACAM + 根号分治，数据结构用的是分块平衡了一下时间，复杂度应该是 $O((n+q+\sum |s_i|) \times \sqrt{\sum |s_i|})$ 的。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e5+10,M = 410;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m,s;


struct Block{
	int B,t,bl[N],L[M],R[M],a[N],sum[M];
	void build(){
		B = sqrt(s),t = (s-1)/B+1;
		for(int i = 1;i <= t;i++)L[i] = (i-1)*B+1,R[i] = min(s,i*B);
		for(int i = 1;i <= s;i++)bl[i] = (i-1)/B+1;
	} 
	void clear(){
		memset(a,0,sizeof a);
		memset(sum,0,sizeof sum);
	}
	void add(int l,int r,int val){
		int ql = bl[l],qr = bl[r];
		if(ql == qr){
			for(int i = l;i <= r;i++)a[i] += val;
			return;
		}
		for(int i = ql+1;i < qr;i++)sum[i] += val;
		for(int i = l;i <= R[ql];i++)a[i] += val;
		for(int i = L[qr];i <= r;i++)a[i] += val;
	} 
	int ask(int x){return a[x] + sum[bl[x]];}
	int ask(int l,int r){return ask(r) - ask(l-1);}
}bl;


int dfn[N],siz[N],id[N]; 
struct ACAM{
	struct node{int son[26];}s[N];
	int fa[N],cnt;
	vector<int>e[N];
	queue<int>q;
	void insert(string c,int num){
		int p = 0;
		for(char i : c){
			int v = i - 'a';
			if(!s[p].son[v])s[p].son[v] = ++cnt;
			p = s[p].son[v];
		}
		id[num] = p;
	}
	void build(){
		for(int i = 0;i < 26;i++)
			if(s[0].son[i])q.push(s[0].son[i]);
		while(!q.empty()){
			int p = q.front();q.pop();
			e[fa[p]].pb(p);
			for(int i = 0;i < 26;i++){
				int v = s[p].son[i];
				if(!v)s[p].son[i] = s[fa[p]].son[i];
				else fa[v] = s[fa[p]].son[i],q.push(v);
			}
		}
		cnt = 0,dfs(0);
	}
	void dfs(int x){
		dfn[x] = ++cnt,siz[x] = 1;
		for(int y : e[x])dfs(y),siz[x] += siz[y];
	}
	int ask(string c){
		int p = 0,ans = 0;
		for(char i : c){
			p = s[p].son[i - 'a'];
			ans += bl.ask(dfn[p]);
		}
		return ans;
	}
	void add(string c,int val){
		int p = 0;
		for(char i : c){
			p = s[p].son[i - 'a'];
			bl.add(dfn[p],cnt,val); 
		}
	}
}Tr;


string c[N];
int len[N];
struct made{int q,f,id;};
vector<made>G1[N],G2[N];
int ans[N];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = read(),m = read();
	for(int i = 1;i <= n;i++){
		cin>>c[i];len[i] = c[i].length();
		Tr.insert(c[i],i);
		s += len[i];
	}
	Tr.build(),bl.build();
	for(int i = 1;i <= m;i++){
		int l = read(),r = read(),k = read();
		if(len[k] <= bl.B)G1[l-1].pb({k,-1,i}),G1[r].pb({k,1,i});
		else G2[k].pb({l,r,i});
	}
	for(int i = 1;i <= n;i++){
		bl.add(dfn[id[i]],dfn[id[i]] + siz[id[i]] - 1,1);
		for(made now : G1[i])ans[now.id] += now.f * Tr.ask(c[now.q]);
		G1[i].clear();
	}
	bl.clear();
	for(int x = 1;x <= n;x++){
		if(len[x] <= bl.B)continue;
		for(made now : G2[x])G1[now.f].pb({0,1,now.id}),G1[now.q-1].pb({0,-1,now.id});
		Tr.add(c[x],1);int s = 0;
		for(int i = 1;i <= n;i++){
			s += bl.ask(dfn[id[i]],dfn[id[i]] + siz[id[i]] - 1);
			for(made now : G1[i])ans[now.id] += s * now.f;
			G1[i].clear();
		}
		Tr.add(c[x],-1);
	}
	for(int i = 1;i <= m;i++)printf("%d\n",ans[i]);

	return 0;

}