#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MAX = 100005;
const int SQRT = 300;
int nxt[MAX][26], f[MAX], state[MAX], sz = 1;
int insert(string &s)
{
int v = 0;
for (int i = 0; i < (int)s.size(); i++)
{
if (nxt[v][s[i] - 'a'] == 0)
nxt[v][s[i] - 'a'] = sz++;
v = nxt[v][s[i] - 'a'];
}
return v;
}
int q[MAX];
void aho()
{
int h = 0, t = 0;
for (int i = 0; i < 26; i++)
if (nxt[0][i])
q[t++] = nxt[0][i];
while (h < t)
{
int v = q[h++];
for (int i = 0; i < 26; i++)
if (nxt[v][i])
{
f[nxt[v][i]] = nxt[f[v]][i];
q[t++] = nxt[v][i];
}
else
nxt[v][i] = nxt[f[v]][i];
}
}
vector<int> adj[MAX];
int st[MAX], fi[MAX], cnt;
void dfs(int v)
{
st[v] = cnt++;
for (int i = 0; i < (int)adj[v].size(); i++)
dfs(adj[v][i]);
fi[v] = cnt;
}
int fen[MAX];
void _add(int p, int val)
{
for (; p > 0; p -= p & -p)
fen[p] += val;
}
void add(int l, int r, int val)
{
_add(r, val);
_add(l, -val);
}
int get(int p)
{
int ans = 0;
for (p++; p < MAX; p += p & -p)
ans += fen[p];
return ans;
}
struct query
{
int r, k, id, sign;
query(int _r = 0, int _k = 0, int _id = 0, int _sign = 0)
{
r = _r;
k = _k;
id = _id;
sign = _sign;
}
} que[2 * MAX];
bool cmp(query x, query y)
{
return (x.r < y.r);
}
vector<query> qq[MAX];
long long ps[MAX], ans[MAX];
int sum[MAX], n;
void pre(int v)
{
for (int i = 0; i < (int)adj[v].size(); i++)
{
int u = adj[v][i];
pre(u);
sum[v] += sum[u];
}
}
string s[MAX];
void solve(int id)
{
memset(sum, 0, sizeof(sum));
int v = 0;
for (int i = 0; i < (int)s[id].size(); i++)
{
v = nxt[v][s[id][i] - 'a'];
sum[v]++;
}
pre(0);
for (int i = 0; i < n; i++)
ps[i + 1] = ps[i] + sum[state[i]];
for (int i = 0; i < (int)qq[id].size(); i++)
ans[qq[id][i].id] += qq[id][i].sign * ps[qq[id][i].r];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> n >> q;
for (int i = 0; i < n; i++)
{
cin >> s[i];
state[i] = insert(s[i]);
}
aho();
for (int i = 1; i < sz; i++)
adj[f[i]].push_back(i);
dfs(0);
sz = 0;
for (int i = 0; i < q; i++)
{
int l, r, k;
cin >> l >> r >> k;
l--;
k--;
if (s[k].size() <= SQRT)
{
que[sz++] = query(r, k, i, 1);
que[sz++] = query(l, k, i, -1);
}
else
{
qq[k].push_back(query(r, k, i, 1));
qq[k].push_back(query(l, k, i, -1));
}
}
for (int i = 0; i < n; i++)
if (s[i].size() > SQRT)
solve(i);
sort(que, que + sz, cmp);
int ptr = 0;
for (int i = 0; i < sz; i++)
{
while (ptr < que[i].r)
{
add(st[state[ptr]], fi[state[ptr]], 1);
ptr++;
}
int v = 0;
for (int j = 0; j < (int)s[que[i].k].size(); j++)
{
v = nxt[v][s[que[i].k][j] - 'a'];
ans[que[i].id] += que[i].sign * get(st[v]);
}
}
for (int i = 0; i < q; i++)
cout << ans[i] << "\n";
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE1BWCA9IDEwMDAwNTsKY29uc3QgaW50IFNRUlQgPSAzMDA7CmludCBueHRbTUFYXVsyNl0sIGZbTUFYXSwgc3RhdGVbTUFYXSwgc3ogPSAxOwppbnQgaW5zZXJ0KHN0cmluZyAmcykKewoJaW50IHYgPSAwOwoJZm9yIChpbnQgaSA9IDA7IGkgPCAoaW50KXMuc2l6ZSgpOyBpKyspCgl7CgkJaWYgKG54dFt2XVtzW2ldIC0gJ2EnXSA9PSAwKQoJCQlueHRbdl1bc1tpXSAtICdhJ10gPSBzeisrOwoJCXYgPSBueHRbdl1bc1tpXSAtICdhJ107Cgl9CglyZXR1cm4gdjsKfQppbnQgcVtNQVhdOwp2b2lkIGFobygpCnsKCWludCBoID0gMCwgdCA9IDA7Cglmb3IgKGludCBpID0gMDsgaSA8IDI2OyBpKyspCgkJaWYgKG54dFswXVtpXSkKCQkJcVt0KytdID0gbnh0WzBdW2ldOwoJd2hpbGUgKGggPCB0KQoJewoJCWludCB2ID0gcVtoKytdOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgMjY7IGkrKykKCQkJaWYgKG54dFt2XVtpXSkKCQkJewoJCQkJZltueHRbdl1baV1dID0gbnh0W2Zbdl1dW2ldOwoJCQkJcVt0KytdID0gbnh0W3ZdW2ldOwoJCQl9CgkJCWVsc2UKCQkJCW54dFt2XVtpXSA9IG54dFtmW3ZdXVtpXTsKCX0KfQp2ZWN0b3I8aW50PiBhZGpbTUFYXTsKaW50IHN0W01BWF0sIGZpW01BWF0sIGNudDsKdm9pZCBkZnMoaW50IHYpCnsKCXN0W3ZdID0gY250Kys7Cglmb3IgKGludCBpID0gMDsgaSA8IChpbnQpYWRqW3ZdLnNpemUoKTsgaSsrKQoJCWRmcyhhZGpbdl1baV0pOwoJZmlbdl0gPSBjbnQ7Cn0KaW50IGZlbltNQVhdOwp2b2lkIF9hZGQoaW50IHAsIGludCB2YWwpCnsKCWZvciAoOyBwID4gMDsgcCAtPSBwICYgLXApCgkJZmVuW3BdICs9IHZhbDsKfQp2b2lkIGFkZChpbnQgbCwgaW50IHIsIGludCB2YWwpCnsKCV9hZGQociwgdmFsKTsKCV9hZGQobCwgLXZhbCk7Cn0KaW50IGdldChpbnQgcCkKewoJaW50IGFucyA9IDA7Cglmb3IgKHArKzsgcCA8IE1BWDsgcCArPSBwICYgLXApCgkJYW5zICs9IGZlbltwXTsKCXJldHVybiBhbnM7Cn0Kc3RydWN0IHF1ZXJ5CnsKCWludCByLCBrLCBpZCwgc2lnbjsKCXF1ZXJ5KGludCBfciA9IDAsIGludCBfayA9IDAsIGludCBfaWQgPSAwLCBpbnQgX3NpZ24gPSAwKQoJewoJCXIgPSBfcjsKCQlrID0gX2s7CgkJaWQgPSBfaWQ7CgkJc2lnbiA9IF9zaWduOwoJfQp9IHF1ZVsyICogTUFYXTsKYm9vbCBjbXAocXVlcnkgeCwgcXVlcnkgeSkKewoJcmV0dXJuICh4LnIgPCB5LnIpOwp9CnZlY3RvcjxxdWVyeT4gcXFbTUFYXTsKbG9uZyBsb25nIHBzW01BWF0sIGFuc1tNQVhdOwppbnQgc3VtW01BWF0sIG47CnZvaWQgcHJlKGludCB2KQp7Cglmb3IgKGludCBpID0gMDsgaSA8IChpbnQpYWRqW3ZdLnNpemUoKTsgaSsrKQoJewoJCWludCB1ID0gYWRqW3ZdW2ldOwoJCXByZSh1KTsKCQlzdW1bdl0gKz0gc3VtW3VdOwoJfQp9CnN0cmluZyBzW01BWF07CnZvaWQgc29sdmUoaW50IGlkKQp7CgltZW1zZXQoc3VtLCAwLCBzaXplb2Yoc3VtKSk7CglpbnQgdiA9IDA7Cglmb3IgKGludCBpID0gMDsgaSA8IChpbnQpc1tpZF0uc2l6ZSgpOyBpKyspCgl7CgkJdiA9IG54dFt2XVtzW2lkXVtpXSAtICdhJ107CgkJc3VtW3ZdKys7Cgl9CglwcmUoMCk7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCQlwc1tpICsgMV0gPSBwc1tpXSArIHN1bVtzdGF0ZVtpXV07Cglmb3IgKGludCBpID0gMDsgaSA8IChpbnQpcXFbaWRdLnNpemUoKTsgaSsrKQoJCWFuc1txcVtpZF1baV0uaWRdICs9IHFxW2lkXVtpXS5zaWduICogcHNbcXFbaWRdW2ldLnJdOwp9CmludCBtYWluKCkKewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJY2luLnRpZSgwKTsKCWludCBxOwoJY2luID4+IG4gPj4gcTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJewoJCWNpbiA+PiBzW2ldOwoJCXN0YXRlW2ldID0gaW5zZXJ0KHNbaV0pOwoJfQoJYWhvKCk7Cglmb3IgKGludCBpID0gMTsgaSA8IHN6OyBpKyspCgkJYWRqW2ZbaV1dLnB1c2hfYmFjayhpKTsKCWRmcygwKTsKCXN6ID0gMDsKCWZvciAoaW50IGkgPSAwOyBpIDwgcTsgaSsrKQoJewoJCWludCBsLCByLCBrOwoJCWNpbiA+PiBsID4+IHIgPj4gazsKCQlsLS07CgkJay0tOwoJCWlmIChzW2tdLnNpemUoKSA8PSBTUVJUKQoJCXsKCQkJcXVlW3N6KytdID0gcXVlcnkociwgaywgaSwgMSk7CgkJCXF1ZVtzeisrXSA9IHF1ZXJ5KGwsIGssIGksIC0xKTsKCQl9CgkJZWxzZQoJCXsKCQkJcXFba10ucHVzaF9iYWNrKHF1ZXJ5KHIsIGssIGksIDEpKTsKCQkJcXFba10ucHVzaF9iYWNrKHF1ZXJ5KGwsIGssIGksIC0xKSk7CgkJfQoJfQoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkJaWYgKHNbaV0uc2l6ZSgpID4gU1FSVCkKCQkJc29sdmUoaSk7Cglzb3J0KHF1ZSwgcXVlICsgc3osIGNtcCk7CglpbnQgcHRyID0gMDsKCWZvciAoaW50IGkgPSAwOyBpIDwgc3o7IGkrKykKCXsKCQl3aGlsZSAocHRyIDwgcXVlW2ldLnIpCgkJewoJCQlhZGQoc3Rbc3RhdGVbcHRyXV0sIGZpW3N0YXRlW3B0cl1dLCAxKTsKCQkJcHRyKys7CgkJfQoJCWludCB2ID0gMDsKCQlmb3IgKGludCBqID0gMDsgaiA8IChpbnQpc1txdWVbaV0ua10uc2l6ZSgpOyBqKyspCgkJewoJCQl2ID0gbnh0W3ZdW3NbcXVlW2ldLmtdW2pdIC0gJ2EnXTsKCQkJYW5zW3F1ZVtpXS5pZF0gKz0gcXVlW2ldLnNpZ24gKiBnZXQoc3Rbdl0pOwoJCX0KCX0KCWZvciAoaW50IGkgPSAwOyBpIDwgcTsgaSsrKQoJCWNvdXQgPDwgYW5zW2ldIDw8ICJcbiI7CglyZXR1cm4gMDsKfQo=