#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 = 1e5 + 100;
int TRIE[maxn][26];
string s[maxn];
int f[maxn], aut[maxn][26], root, nx = 1;
vi tof[maxn];
vi adj[maxn];
int end[maxn];
vi ends[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;
++ nx;
}
v = TRIE[v][c];
}
::end[x] = v;
::ends[v].pb(x);
}
inline void ahoc(){
f[root] = root;
queue<int> q;
q.push(root);
while(!q.empty()){
int v = q.front();
q.pop();
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;
q.push(TRIE[v][c]);
}
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];
char ch[maxn];
const int K = 350;
struct sqrt_decomposition{
ll sum[maxn] = {}, tot[K] = {};
inline void add(int p, ll val){
while(p < maxn && p % K)
sum[p ++] += val;
while(p < maxn){
tot[p/K] += val;
p += K;
}
}
inline ll ask(int p){
return (p < 0 ? 0 : sum[p] + tot[p/K]);
}
}SQRT;
struct query{
int l, r, k;
ll ans = 0LL;
query(){}
query(int L, int R, int K){
l = L;
r = R;
k = K;
}
}Q[maxn];
vi queries[maxn];
inline void dfs(int v){
rep(a, ::ends[v])
SQRT.add(a, 1);
rep(i, tof[v]) if((int)s[i].size() < K){
rep(j, queries[i])
Q[j].ans += SQRT.ask(Q[j].r) - SQRT.ask(Q[j].l - 1);
}
rep(u, adj[v]) dfs(u);
rep(a, ::ends[v])
SQRT.add(a, -1);
}
ll ps[maxn];
inline int dfs(int v, int x){
int cnt = 0;
rep(a, tof[v]) if(a == x)
++ cnt;
rep(u, adj[v])
cnt += dfs(u, x);
rep(a, ::ends[v])
ps[a] += (ll)cnt;
return cnt;
}
int main(){
memset(TRIE, -1, sizeof TRIE);
memset(par, -1, sizeof par);
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);
}
For(i,0,q){
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
-- l, -- r, -- k;
Q[i] = query(l, r, k);
queries[k].pb(i);
}
For(i,0,n) if((int)s[i].size() >= K){
fill(ps, ps + maxn, 0LL);
dfs(root, i);
For(i,1,maxn)
ps[i] += ps[i-1];
rep(j, queries[i])
Q[j].ans += ps[Q[j].r] - (Q[j].l ? ps[Q[j].l-1] : 0LL);
}
dfs(root);
For(i,0,q)
printf("%lld\n", Q[i].ans);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIEZvcmVhY2goaSwgYykgZm9yKF9fdHlwZW9mKChjKS5iZWdpbigpKSBpID0gKGMpLmJlZ2luKCk7IGkgIT0gKGMpLmVuZCgpOyArK2kpCiNkZWZpbmUgRm9yKGksYSxiKSBmb3IoaW50IChpKT0oYSk7KGkpIDwgKGIpOyArKyhpKSkKI2RlZmluZSByb2YoaSxhLGIpIGZvcihpbnQgKGkpPShhKTsoaSkgPiAoYik7IC0tKGkpKQojZGVmaW5lIHJlcChpLCBjKSBmb3IoYXV0byAmKGkpIDogKGMpKQojZGVmaW5lIHggZmlyc3QKI2RlZmluZSB5IHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIFBCIHBvcF9iYWNrKCkKI2RlZmluZSBpT1MgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSkKI2RlZmluZSBzcXIoYSkgKCgoYSkgKiAoYSkpKQojZGVmaW5lIGFsbChhKSBhLmJlZ2luKCkgLCBhLmVuZCgpCiNkZWZpbmUgZXJyb3IoeCkgY2VyciA8PCAjeCA8PCAiID0gIiA8PCAoeCkgPDxlbmRsCiNkZWZpbmUgRXJyb3IoYSxiKSBjZXJyPDwiKCAiPDwjYTw8IiAsICI8PCNiPDwiICkgPSAoICI8PChhKTw8IiAsICI8PChiKTw8IiApXG4iOwojZGVmaW5lIGVycm9wKGEpIGNlcnI8PCNhPDwiID0gKCAiPDwoKGEpLngpPDwiICwgIjw8KChhKS55KTw8IiApXG4iOwojZGVmaW5lIGNvdWQoYSxiKSBjb3V0PDxmaXhlZCA8PCBzZXRwcmVjaXNpb24oKGIpKSA8PCAoYSkKI2RlZmluZSBMKHgpICgoeCk8PDEpCiNkZWZpbmUgUih4KSAoKCh4KTw8MSkrMSkKI2RlZmluZSB1bWFwIHVub3JkZXJlZF9tYXAKI2RlZmluZSBkb3VibGUgbG9uZyBkb3VibGUKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxpbnQsaW50PnBpaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBjb21wbGV4PGRvdWJsZT4gcG9pbnQ7CnRlbXBsYXRlIDx0eXBlbmFtZSBUPiB1c2luZyBvcyA9ICB0cmVlPFQsIG51bGxfdHlwZSwgbGVzczxUPiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT47CnRlbXBsYXRlIDxjbGFzcyBUPiAgaW5saW5lIHZvaWQgc21heChUICZ4LFQgeSl7IHggPSBtYXgoKHgpLCAoeSkpO30KdGVtcGxhdGUgPGNsYXNzIFQ+ICBpbmxpbmUgdm9pZCBzbWluKFQgJngsVCB5KXsgeCA9IG1pbigoeCksICh5KSk7fQpjb25zdCBpbnQgbWF4biA9IDFlNSArIDEwMDsKaW50IFRSSUVbbWF4bl1bMjZdOwpzdHJpbmcgc1ttYXhuXTsKaW50IGZbbWF4bl0sIGF1dFttYXhuXVsyNl0sIHJvb3QsIG54ID0gMTsKdmkgdG9mW21heG5dOwp2aSBhZGpbbWF4bl07CmludCBlbmRbbWF4bl07CnZpIGVuZHNbbWF4bl07CmlubGluZSB2b2lkIGJ1aWxkKGludCB4KXsKCWludCB2ID0gcm9vdDsKCXJlcChjaCwgc1t4XSl7CgkJaW50IGMgPSBjaCAtICdhJzsKCQlpZihUUklFW3ZdW2NdID09IC0xKXsKCQkJVFJJRVt2XVtjXSA9IG54OwoJCQkrKyBueDsKCQl9CgkJdiA9IFRSSUVbdl1bY107Cgl9Cgk6OmVuZFt4XSA9IHY7Cgk6OmVuZHNbdl0ucGIoeCk7Cn0KaW5saW5lIHZvaWQgYWhvYygpewoJZltyb290XSA9IHJvb3Q7CglxdWV1ZTxpbnQ+IHE7CglxLnB1c2gocm9vdCk7Cgl3aGlsZSghcS5lbXB0eSgpKXsKCQlpbnQgdiA9IHEuZnJvbnQoKTsKCQlxLnBvcCgpOwoJCUZvcihjLDAsMjYpewoJCQlpZihUUklFW3ZdW2NdICE9IC0xKXsKCQkJCWF1dFt2XVtjXSA9IFRSSUVbdl1bY107CQoJCQkJaWYodiAhPSByb290KQoJCQkJCWZbYXV0W3ZdW2NdXSA9IGF1dFtmW3ZdXVtjXTsKCQkJCWVsc2UKCQkJCQlmW2F1dFt2XVtjXV0gPSByb290OwoJCQkJcS5wdXNoKFRSSUVbdl1bY10pOwoJCQl9CgkJCWVsc2V7CgkJCQlpZih2ID09IHJvb3QpCgkJCQkJYXV0W3ZdW2NdID0gcm9vdDsKCQkJCWVsc2UKCQkJCQlhdXRbdl1bY10gPSBhdXRbZlt2XV1bY107CgkJCX0KCQl9Cgl9Cn0KaW5saW5lIHZvaWQgZ28oaW50IHgpewoJaW50IHYgPSByb290OwoJcmVwKGNoLCBzW3hdKXsKCQlpbnQgYyA9IGNoIC0gJ2EnOwoJCXYgPSBhdXRbdl1bY107CgkJdG9mW3ZdLnBiKHgpOwoJfQp9CmludCBwYXJbbWF4bl07CmNoYXIgY2hbbWF4bl07CmNvbnN0IGludCBLID0gMzUwOwpzdHJ1Y3Qgc3FydF9kZWNvbXBvc2l0aW9uewoJbGwgc3VtW21heG5dID0ge30sIHRvdFtLXSA9IHt9OwoJaW5saW5lIHZvaWQgYWRkKGludCBwLCBsbCB2YWwpewoJCXdoaWxlKHAgPCBtYXhuICYmIHAgJSBLKQoJCQlzdW1bcCArK10gKz0gdmFsOwoJCXdoaWxlKHAgPCBtYXhuKXsKCQkJdG90W3AvS10gKz0gdmFsOwoJCQlwICs9IEs7CgkJfQoJfQoJaW5saW5lIGxsIGFzayhpbnQgcCl7CgkJcmV0dXJuIChwIDwgMCA/IDAgOiBzdW1bcF0gKyB0b3RbcC9LXSk7Cgl9Cn1TUVJUOwpzdHJ1Y3QgcXVlcnl7CglpbnQgbCwgciwgazsKCWxsIGFucyA9IDBMTDsKCXF1ZXJ5KCl7fQoJcXVlcnkoaW50IEwsIGludCBSLCBpbnQgSyl7CgkJbCA9IEw7CgkJciA9IFI7CgkJayA9IEs7Cgl9Cn1RW21heG5dOwp2aSBxdWVyaWVzW21heG5dOwppbmxpbmUgdm9pZCBkZnMoaW50IHYpewoJcmVwKGEsIDo6ZW5kc1t2XSkKCQlTUVJULmFkZChhLCAxKTsKCXJlcChpLCB0b2Zbdl0pCWlmKChpbnQpc1tpXS5zaXplKCkgPCBLKXsKCQlyZXAoaiwgcXVlcmllc1tpXSkKCQkJUVtqXS5hbnMgKz0gU1FSVC5hc2soUVtqXS5yKSAtIFNRUlQuYXNrKFFbal0ubCAtIDEpOwoJfQoJcmVwKHUsIGFkalt2XSkJZGZzKHUpOwoJcmVwKGEsIDo6ZW5kc1t2XSkKCQlTUVJULmFkZChhLCAtMSk7Cn0KbGwgcHNbbWF4bl07CmlubGluZSBpbnQgZGZzKGludCB2LCBpbnQgeCl7CglpbnQgY250ID0gMDsKCXJlcChhLCB0b2Zbdl0pCWlmKGEgPT0geCkKCQkrKyBjbnQ7CglyZXAodSwgYWRqW3ZdKQoJCWNudCArPSBkZnModSwgeCk7CglyZXAoYSwgOjplbmRzW3ZdKQoJCXBzW2FdICs9IChsbCljbnQ7CglyZXR1cm4gY250Owp9CmludCBtYWluKCl7CgltZW1zZXQoVFJJRSwgLTEsIHNpemVvZiBUUklFKTsKCW1lbXNldChwYXIsIC0xLCBzaXplb2YgcGFyKTsKCWludCBuLCBxOwoJc2NhbmYoIiVkICVkIiwgJm4sICZxKTsKCUZvcihpLDAsbil7CgkJc2NhbmYoIiVzIiwgY2gpOwoJCXNbaV0gPSAoc3RyaW5nKWNoOwoJCWJ1aWxkKGkpOwoJfQoJYWhvYygpOwoJRm9yKGksMCxuKQoJCWdvKGkpOwoJRm9yKGksMSxueCl7CgkJcGFyW2ldID0gZltpXTsKCQlhZGpbcGFyW2ldXS5wYihpKTsKCX0KCUZvcihpLDAscSl7CgkJaW50IGwsIHIsIGs7CgkJc2NhbmYoIiVkICVkICVkIiwgJmwsICZyLCAmayk7CgkJLS0gbCwgLS0gciwgLS0gazsKCQlRW2ldID0gcXVlcnkobCwgciwgayk7CgkJcXVlcmllc1trXS5wYihpKTsKCX0KCUZvcihpLDAsbikJaWYoKGludClzW2ldLnNpemUoKSA+PSBLKXsKCQlmaWxsKHBzLCBwcyArIG1heG4sIDBMTCk7CgkJZGZzKHJvb3QsIGkpOwoJCUZvcihpLDEsbWF4bikKCQkJcHNbaV0gKz0gcHNbaS0xXTsKCQlyZXAoaiwgcXVlcmllc1tpXSkKCQkJUVtqXS5hbnMgKz0gcHNbUVtqXS5yXSAtIChRW2pdLmwgPyBwc1tRW2pdLmwtMV0gOiAwTEwpOwoJfQoJZGZzKHJvb3QpOwoJRm9yKGksMCxxKQoJCXByaW50ZigiJWxsZFxuIiwgUVtpXS5hbnMpOwoJcmV0dXJuIDA7Cn0KCg==