#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
#define rep(i, c) for(auto &(i) : (c))
#define x first
#define y second
#define pb push_back
#define PB pop_back()
#define iOS ios_base::sync_with_stdio(false)
#define sqr(a) (((a) * (a)))
#define all(a) a.begin() , a.end()
#define error(x) cerr << #x << " = " << (x) <<endl
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define umap unordered_map
#define double long double
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int> vi;
typedef complex<double> point;
template <typename T> using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> inline void smax(T &x,T y){ x = max((x), (y));}
template <class T> inline void smin(T &x,T y){ x = min((x), (y));}
const int maxn = 5e5 + 100;
int TRIE[maxn][26];
string s[maxn];
int f[maxn], aut[maxn][26], root, nx = 1;
vi tof[maxn];
int h[maxn];
vi ver[maxn];
vi adj[maxn];
int end[maxn];
inline void build(int x){
int v = root;
rep(ch, s[x]){
int c = ch - 'a';
if(TRIE[v][c] == -1){
TRIE[v][c] = nx;
h[nx] = h[v] + 1;
ver[h[nx]].pb(nx);
++ nx;
}
v = TRIE[v][c];
}
::end[x] = v;
}
inline void ahoc(){
f[root] = root;
For(h,0,maxn)
rep(v, ver[h])For(c,0,26){
if(TRIE[v][c] != -1){
aut[v][c] = TRIE[v][c];
if(v != root)
f[aut[v][c]] = aut[f[v]][c];
else
f[aut[v][c]] = root;
}
else{
if(v == root)
aut[v][c] = root;
else
aut[v][c] = aut[f[v]][c];
}
}
}
inline void go(int x){
int v = root;
rep(ch, s[x]){
int c = ch - 'a';
v = aut[v][c];
tof[v].pb(x);
}
}
int par[maxn];
int st[maxn], ft[maxn];
int a[maxn], nex = 0;
inline void dfs(int v){
st[v] = nex;
rep(x, tof[v])
a[nex ++] = x;
rep(u, adj[v])
dfs(u);
ft[v] = nex;
}
vi seg[maxn * 4];
inline void segbuild(int id = 1,int l = 0,int r = nex){
if(r - l < 2){
seg[id].pb(a[l]);
return ;
}
int mid = (l+r)/2;
segbuild(L(id), l, mid);
segbuild(R(id), mid, r);
merge(all(seg[L(id)]), all(seg[R(id)]), back_inserter(seg[id]));
}
inline int ask(int x, int y, int a,int b,int id = 1,int l = 0,int r = nex){
if(l >= y or x >= r)
return 0;
if(x <= l && r <= y)
return upper_bound(all(seg[id]), b) - upper_bound(all(seg[id]), a-1);
int mid = (l+r)/2;
return ask(x, y, a, b, L(id), l, mid) +
ask(x, y, a, b, R(id), mid, r) ;
}
char ch[maxn];
int main(){
memset(TRIE, -1, sizeof TRIE);
memset(par, -1, sizeof par);
ver[0].pb(root);
int n, q;
scanf("%d %d", &n, &q);
For(i,0,n){
scanf("%s", ch);
s[i] = (string)ch;
build(i);
}
ahoc();
For(i,0,n)
go(i);
For(i,1,nx){
par[i] = f[i];
adj[par[i]].pb(i);
}
dfs(root);
segbuild();
For(i,0,q){
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
-- l, -- k, -- r;
k = ::end[k];
printf("%d\n", ask(st[k], ft[k], l, r));
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIEZvcmVhY2goaSwgYykgZm9yKF9fdHlwZW9mKChjKS5iZWdpbigpKSBpID0gKGMpLmJlZ2luKCk7IGkgIT0gKGMpLmVuZCgpOyArK2kpCiNkZWZpbmUgRm9yKGksYSxiKSBmb3IoaW50IChpKT0oYSk7KGkpIDwgKGIpOyArKyhpKSkKI2RlZmluZSByb2YoaSxhLGIpIGZvcihpbnQgKGkpPShhKTsoaSkgPiAoYik7IC0tKGkpKQojZGVmaW5lIHJlcChpLCBjKSBmb3IoYXV0byAmKGkpIDogKGMpKQojZGVmaW5lIHggZmlyc3QKI2RlZmluZSB5IHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIFBCIHBvcF9iYWNrKCkKI2RlZmluZSBpT1MgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSkKI2RlZmluZSBzcXIoYSkgKCgoYSkgKiAoYSkpKQojZGVmaW5lIGFsbChhKSBhLmJlZ2luKCkgLCBhLmVuZCgpCiNkZWZpbmUgZXJyb3IoeCkgY2VyciA8PCAjeCA8PCAiID0gIiA8PCAoeCkgPDxlbmRsCiNkZWZpbmUgRXJyb3IoYSxiKSBjZXJyPDwiKCAiPDwjYTw8IiAsICI8PCNiPDwiICkgPSAoICI8PChhKTw8IiAsICI8PChiKTw8IiApXG4iOwojZGVmaW5lIGVycm9wKGEpIGNlcnI8PCNhPDwiID0gKCAiPDwoKGEpLngpPDwiICwgIjw8KChhKS55KTw8IiApXG4iOwojZGVmaW5lIGNvdWQoYSxiKSBjb3V0PDxmaXhlZCA8PCBzZXRwcmVjaXNpb24oKGIpKSA8PCAoYSkKI2RlZmluZSBMKHgpICgoeCk8PDEpCiNkZWZpbmUgUih4KSAoKCh4KTw8MSkrMSkKI2RlZmluZSB1bWFwIHVub3JkZXJlZF9tYXAKI2RlZmluZSBkb3VibGUgbG9uZyBkb3VibGUKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxpbnQsaW50PnBpaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBjb21wbGV4PGRvdWJsZT4gcG9pbnQ7CnRlbXBsYXRlIDx0eXBlbmFtZSBUPiB1c2luZyBvcyA9ICB0cmVlPFQsIG51bGxfdHlwZSwgbGVzczxUPiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT47CnRlbXBsYXRlIDxjbGFzcyBUPiAgaW5saW5lIHZvaWQgc21heChUICZ4LFQgeSl7IHggPSBtYXgoKHgpLCAoeSkpO30KdGVtcGxhdGUgPGNsYXNzIFQ+ICBpbmxpbmUgdm9pZCBzbWluKFQgJngsVCB5KXsgeCA9IG1pbigoeCksICh5KSk7fQpjb25zdCBpbnQgbWF4biA9IDVlNSArIDEwMDsKaW50IFRSSUVbbWF4bl1bMjZdOwpzdHJpbmcgc1ttYXhuXTsKaW50IGZbbWF4bl0sIGF1dFttYXhuXVsyNl0sIHJvb3QsIG54ID0gMTsKdmkgdG9mW21heG5dOwppbnQgaFttYXhuXTsKdmkgdmVyW21heG5dOwp2aSBhZGpbbWF4bl07CmludCBlbmRbbWF4bl07CmlubGluZSB2b2lkIGJ1aWxkKGludCB4KXsKCWludCB2ID0gcm9vdDsKCXJlcChjaCwgc1t4XSl7CgkJaW50IGMgPSBjaCAtICdhJzsKCQlpZihUUklFW3ZdW2NdID09IC0xKXsKCQkJVFJJRVt2XVtjXSA9IG54OwoJCQloW254XSA9IGhbdl0gKyAxOwoJCQl2ZXJbaFtueF1dLnBiKG54KTsKCQkJKysgbng7CgkJfQoJCXYgPSBUUklFW3ZdW2NdOwoJfQoJOjplbmRbeF0gPSB2Owp9CmlubGluZSB2b2lkIGFob2MoKXsKCWZbcm9vdF0gPSByb290OwoJRm9yKGgsMCxtYXhuKQoJCXJlcCh2LCB2ZXJbaF0pRm9yKGMsMCwyNil7CgkJCWlmKFRSSUVbdl1bY10gIT0gLTEpewoJCQkJYXV0W3ZdW2NdID0gVFJJRVt2XVtjXTsJCgkJCQlpZih2ICE9IHJvb3QpCgkJCQkJZlthdXRbdl1bY11dID0gYXV0W2Zbdl1dW2NdOwoJCQkJZWxzZQoJCQkJCWZbYXV0W3ZdW2NdXSA9IHJvb3Q7CgkJCX0KCQkJZWxzZXsKCQkJCWlmKHYgPT0gcm9vdCkKCQkJCQlhdXRbdl1bY10gPSByb290OwoJCQkJZWxzZQoJCQkJCWF1dFt2XVtjXSA9IGF1dFtmW3ZdXVtjXTsKCQkJfQoJCX0KfQppbmxpbmUgdm9pZCBnbyhpbnQgeCl7CglpbnQgdiA9IHJvb3Q7CglyZXAoY2gsIHNbeF0pewoJCWludCBjID0gY2ggLSAnYSc7CgkJdiA9IGF1dFt2XVtjXTsKCQl0b2Zbdl0ucGIoeCk7Cgl9Cn0KaW50IHBhclttYXhuXTsKaW50IHN0W21heG5dLCBmdFttYXhuXTsKaW50IGFbbWF4bl0sIG5leCA9IDA7CmlubGluZSB2b2lkIGRmcyhpbnQgdil7CglzdFt2XSA9IG5leDsKCXJlcCh4LCB0b2Zbdl0pCgkJYVtuZXggKytdID0geDsKCXJlcCh1LCBhZGpbdl0pCgkJZGZzKHUpOwoJZnRbdl0gPSBuZXg7Cn0Kdmkgc2VnW21heG4gKiA0XTsKaW5saW5lIHZvaWQgc2VnYnVpbGQoaW50IGlkID0gMSxpbnQgbCA9IDAsaW50IHIgPSBuZXgpewoJaWYociAtIGwgPCAyKXsKCQlzZWdbaWRdLnBiKGFbbF0pOwoJCXJldHVybiA7Cgl9CglpbnQgbWlkID0gKGwrcikvMjsKCXNlZ2J1aWxkKEwoaWQpLCBsLCBtaWQpOwoJc2VnYnVpbGQoUihpZCksIG1pZCwgcik7CgltZXJnZShhbGwoc2VnW0woaWQpXSksIGFsbChzZWdbUihpZCldKSwgYmFja19pbnNlcnRlcihzZWdbaWRdKSk7Cn0KaW5saW5lIGludCBhc2soaW50IHgsIGludCB5LCBpbnQgYSxpbnQgYixpbnQgaWQgPSAxLGludCBsID0gMCxpbnQgciA9IG5leCl7CglpZihsID49IHkgb3IgeCA+PSByKQoJCXJldHVybiAwOwoJaWYoeCA8PSBsICYmIHIgPD0geSkKCQlyZXR1cm4gdXBwZXJfYm91bmQoYWxsKHNlZ1tpZF0pLCBiKSAtIHVwcGVyX2JvdW5kKGFsbChzZWdbaWRdKSwgYS0xKTsKCWludCBtaWQgPSAobCtyKS8yOwoJcmV0dXJuIGFzayh4LCB5LCBhLCBiLCBMKGlkKSwgbCwgbWlkKSArCgkJICAgYXNrKHgsIHksIGEsIGIsIFIoaWQpLCBtaWQsIHIpIDsKfQpjaGFyIGNoW21heG5dOwppbnQgbWFpbigpewoJbWVtc2V0KFRSSUUsIC0xLCBzaXplb2YgVFJJRSk7CgltZW1zZXQocGFyLCAtMSwgc2l6ZW9mIHBhcik7Cgl2ZXJbMF0ucGIocm9vdCk7CglpbnQgbiwgcTsKCXNjYW5mKCIlZCAlZCIsICZuLCAmcSk7CglGb3IoaSwwLG4pewoJCXNjYW5mKCIlcyIsIGNoKTsKCQlzW2ldID0gKHN0cmluZyljaDsKCQlidWlsZChpKTsKCX0KCWFob2MoKTsKCUZvcihpLDAsbikKCQlnbyhpKTsKCUZvcihpLDEsbngpewoJCXBhcltpXSA9IGZbaV07CgkJYWRqW3BhcltpXV0ucGIoaSk7Cgl9CglkZnMocm9vdCk7CglzZWdidWlsZCgpOwoJRm9yKGksMCxxKXsKCQlpbnQgbCwgciwgazsKCQlzY2FuZigiJWQgJWQgJWQiLCAmbCwgJnIsICZrKTsKCQktLSBsLCAtLSBrLCAtLSByOwoJCWsgPSA6OmVuZFtrXTsKCQlwcmludGYoIiVkXG4iLCBhc2soc3Rba10sIGZ0W2tdLCBsLCByKSk7Cgl9Cn0KCg==