#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];
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;
++ nx;
}
v = TRIE[v][c];
}
::end[x] = v;
}
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];
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;
}
struct query{
int l, r, k, ind, sgn;
query(){
l = r = k = 0;
}
query(int L,int R,int K,int IND,int SGN){l = L, r = R, k = K, ind = IND, sgn = SGN;}
bool operator < (const query &a) const{
if(k != a.k)
return k < a.k;
return pii(l, r) < pii(a.l, a.r);
}
};
pii p[maxn];
int fen[maxn];
inline void add(int x){
++ x;
for(int i = x;i < maxn;i += i & -i)
fen[i] ++;
}
inline int ask(int x){
++ x;
int res = 0;
for(int i = x;i > 0;i -= i & -i)
res += fen[i];
return res;
}
inline int ask(int l, int r){
return max(0, ask(r) - ask(l-1));
}
int answ[maxn];
vector<query> quer;
int lq[maxn], rq[maxn], kq[maxn];
char ch[maxn];
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);
}
dfs(root);
For(i,0,q){
scanf("%d %d %d", lq + i, rq + i, kq + i);
-- kq[i];
kq[i] = ::end[kq[i]];
lq[i] --;
rq[i] --;
quer.pb(query(st[kq[i]], ft[kq[i]] - 1, lq[i] - 1, i, -1));
quer.pb(query(st[kq[i]], ft[kq[i]] - 1, rq[i], i, 1));
}
sort(all(quer));
For(i,0,nex)
p[i] = {a[i], i};
sort(p, p + nex);
int po = 0;
rep(q, quer){
int l = q.l;
int r = q.r;
int k = q.k;
while(po < nex && p[po].x <= k){
add(p[po].y);
po ++;
}
int ans = ask(l, r);
int ind = q.ind;
answ[ind] += q.sgn * ans;
}
For(i,0,q)
printf("%d\n", answ[i] );
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIEZvcmVhY2goaSwgYykgZm9yKF9fdHlwZW9mKChjKS5iZWdpbigpKSBpID0gKGMpLmJlZ2luKCk7IGkgIT0gKGMpLmVuZCgpOyArK2kpCiNkZWZpbmUgRm9yKGksYSxiKSBmb3IoaW50IChpKT0oYSk7KGkpIDwgKGIpOyArKyhpKSkKI2RlZmluZSByb2YoaSxhLGIpIGZvcihpbnQgKGkpPShhKTsoaSkgPiAoYik7IC0tKGkpKQojZGVmaW5lIHJlcChpLCBjKSBmb3IoYXV0byAmKGkpIDogKGMpKQojZGVmaW5lIHggZmlyc3QKI2RlZmluZSB5IHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIFBCIHBvcF9iYWNrKCkKI2RlZmluZSBpT1MgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSkKI2RlZmluZSBzcXIoYSkgKCgoYSkgKiAoYSkpKQojZGVmaW5lIGFsbChhKSBhLmJlZ2luKCkgLCBhLmVuZCgpCiNkZWZpbmUgZXJyb3IoeCkgY2VyciA8PCAjeCA8PCAiID0gIiA8PCAoeCkgPDxlbmRsCiNkZWZpbmUgRXJyb3IoYSxiKSBjZXJyPDwiKCAiPDwjYTw8IiAsICI8PCNiPDwiICkgPSAoICI8PChhKTw8IiAsICI8PChiKTw8IiApXG4iOwojZGVmaW5lIGVycm9wKGEpIGNlcnI8PCNhPDwiID0gKCAiPDwoKGEpLngpPDwiICwgIjw8KChhKS55KTw8IiApXG4iOwojZGVmaW5lIGNvdWQoYSxiKSBjb3V0PDxmaXhlZCA8PCBzZXRwcmVjaXNpb24oKGIpKSA8PCAoYSkKI2RlZmluZSBMKHgpICgoeCk8PDEpCiNkZWZpbmUgUih4KSAoKCh4KTw8MSkrMSkKI2RlZmluZSB1bWFwIHVub3JkZXJlZF9tYXAKI2RlZmluZSBkb3VibGUgbG9uZyBkb3VibGUKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxpbnQsaW50PnBpaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBjb21wbGV4PGRvdWJsZT4gcG9pbnQ7CnRlbXBsYXRlIDx0eXBlbmFtZSBUPiB1c2luZyBvcyA9ICB0cmVlPFQsIG51bGxfdHlwZSwgbGVzczxUPiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT47CnRlbXBsYXRlIDxjbGFzcyBUPiAgaW5saW5lIHZvaWQgc21heChUICZ4LFQgeSl7IHggPSBtYXgoKHgpLCAoeSkpO30KdGVtcGxhdGUgPGNsYXNzIFQ+ICBpbmxpbmUgdm9pZCBzbWluKFQgJngsVCB5KXsgeCA9IG1pbigoeCksICh5KSk7fQpjb25zdCBpbnQgbWF4biA9IDVlNSArIDEwMDsKaW50IFRSSUVbbWF4bl1bMjZdOwpzdHJpbmcgc1ttYXhuXTsKaW50IGZbbWF4bl0sIGF1dFttYXhuXVsyNl0sIHJvb3QsIG54ID0gMTsKdmkgdG9mW21heG5dOwp2aSBhZGpbbWF4bl07CmludCBlbmRbbWF4bl07CmlubGluZSB2b2lkIGJ1aWxkKGludCB4KXsKCWludCB2ID0gcm9vdDsKCXJlcChjaCwgc1t4XSl7CgkJaW50IGMgPSBjaCAtICdhJzsKCQlpZihUUklFW3ZdW2NdID09IC0xKXsKCQkJVFJJRVt2XVtjXSA9IG54OwoJCQkrKyBueDsKCQl9CgkJdiA9IFRSSUVbdl1bY107Cgl9Cgk6OmVuZFt4XSA9IHY7Cn0KaW5saW5lIHZvaWQgYWhvYygpewoJZltyb290XSA9IHJvb3Q7CglxdWV1ZTxpbnQ+IHE7CglxLnB1c2gocm9vdCk7Cgl3aGlsZSghcS5lbXB0eSgpKXsKCQlpbnQgdiA9IHEuZnJvbnQoKTsKCQlxLnBvcCgpOwoJCUZvcihjLDAsMjYpewoJCQlpZihUUklFW3ZdW2NdICE9IC0xKXsKCQkJCWF1dFt2XVtjXSA9IFRSSUVbdl1bY107CQoJCQkJaWYodiAhPSByb290KQoJCQkJCWZbYXV0W3ZdW2NdXSA9IGF1dFtmW3ZdXVtjXTsKCQkJCWVsc2UKCQkJCQlmW2F1dFt2XVtjXV0gPSByb290OwoJCQkJcS5wdXNoKFRSSUVbdl1bY10pOwoJCQl9CgkJCWVsc2V7CgkJCQlpZih2ID09IHJvb3QpCgkJCQkJYXV0W3ZdW2NdID0gcm9vdDsKCQkJCWVsc2UKCQkJCQlhdXRbdl1bY10gPSBhdXRbZlt2XV1bY107CgkJCX0KCQl9Cgl9Cn0KaW5saW5lIHZvaWQgZ28oaW50IHgpewoJaW50IHYgPSByb290OwoJcmVwKGNoLCBzW3hdKXsKCQlpbnQgYyA9IGNoIC0gJ2EnOwoJCXYgPSBhdXRbdl1bY107CgkJdG9mW3ZdLnBiKHgpOwoJfQp9CmludCBwYXJbbWF4bl07CmludCBzdFttYXhuXSwgZnRbbWF4bl07CmludCBhW21heG5dLCBuZXggPSAwOwppbmxpbmUgdm9pZCBkZnMoaW50IHYpewoJc3Rbdl0gPSBuZXg7CglyZXAoeCwgdG9mW3ZdKQoJCWFbbmV4ICsrXSA9IHg7CglyZXAodSwgYWRqW3ZdKQoJCWRmcyh1KTsKCWZ0W3ZdID0gbmV4Owp9CnN0cnVjdCBxdWVyeXsKCWludCBsLCByLCBrLCBpbmQsIHNnbjsKCXF1ZXJ5KCl7CgkJbCA9IHIgPSBrID0gMDsKCX0KCXF1ZXJ5KGludCBMLGludCBSLGludCBLLGludCBJTkQsaW50IFNHTil7bCA9IEwsIHIgPSBSLCBrID0gSywgaW5kID0gSU5ELCBzZ24gPSBTR047fQoJYm9vbCBvcGVyYXRvciA8IChjb25zdCBxdWVyeSAmYSkgY29uc3R7CgkJaWYoayAhPSBhLmspCgkJCXJldHVybiBrIDwgYS5rOwoJCXJldHVybiBwaWkobCwgcikgPCBwaWkoYS5sLCBhLnIpOwoJfQp9OwpwaWkgcFttYXhuXTsKaW50IGZlblttYXhuXTsKaW5saW5lIHZvaWQgYWRkKGludCB4KXsKCSsrIHg7Cglmb3IoaW50IGkgPSB4O2kgPCBtYXhuO2kgKz0gaSAmIC1pKQoJCWZlbltpXSArKzsKfQppbmxpbmUgaW50IGFzayhpbnQgeCl7CgkrKyB4OwoJaW50IHJlcyA9IDA7Cglmb3IoaW50IGkgPSB4O2kgPiAwO2kgLT0gaSAmIC1pKQoJCXJlcyArPSBmZW5baV07CglyZXR1cm4gcmVzOwp9CmlubGluZSBpbnQgYXNrKGludCBsLCBpbnQgcil7CglyZXR1cm4gbWF4KDAsIGFzayhyKSAtIGFzayhsLTEpKTsKfQppbnQgYW5zd1ttYXhuXTsKdmVjdG9yPHF1ZXJ5PiBxdWVyOwppbnQgbHFbbWF4bl0sIHJxW21heG5dLCBrcVttYXhuXTsKY2hhciBjaFttYXhuXTsKaW50IG1haW4oKXsKCW1lbXNldChUUklFLCAtMSwgc2l6ZW9mIFRSSUUpOwoJbWVtc2V0KHBhciwgLTEsIHNpemVvZiBwYXIpOwoJaW50IG4sIHE7CglzY2FuZigiJWQgJWQiLCAmbiwgJnEpOwoJRm9yKGksMCxuKXsKCQlzY2FuZigiJXMiLCBjaCk7CgkJc1tpXSA9IChzdHJpbmcpY2g7CgkJYnVpbGQoaSk7Cgl9CglhaG9jKCk7CglGb3IoaSwwLG4pCgkJZ28oaSk7CglGb3IoaSwxLG54KXsKCQlwYXJbaV0gPSBmW2ldOwoJCWFkaltwYXJbaV1dLnBiKGkpOwoJfQoJZGZzKHJvb3QpOwoJRm9yKGksMCxxKXsKCQlzY2FuZigiJWQgJWQgJWQiLCBscSArIGksIHJxICsgaSwga3EgKyBpKTsKCQktLSBrcVtpXTsKCQlrcVtpXSA9IDo6ZW5kW2txW2ldXTsKCQlscVtpXSAtLTsKCQlycVtpXSAtLTsKCQlxdWVyLnBiKHF1ZXJ5KHN0W2txW2ldXSwgZnRba3FbaV1dIC0gMSwgbHFbaV0gLSAxLCBpLCAtMSkpOwoJCXF1ZXIucGIocXVlcnkoc3Rba3FbaV1dLCBmdFtrcVtpXV0gLSAxLCBycVtpXSwgaSwgMSkpOwoJfQoJc29ydChhbGwocXVlcikpOwoJRm9yKGksMCxuZXgpCgkJcFtpXSA9IHthW2ldLCBpfTsKCXNvcnQocCwgcCArIG5leCk7CglpbnQgcG8gPSAwOwoJcmVwKHEsIHF1ZXIpewoJCWludCBsID0gcS5sOwoJCWludCByID0gcS5yOwoJCWludCBrID0gcS5rOwoJCXdoaWxlKHBvIDwgbmV4ICYmIHBbcG9dLnggPD0gayl7CgkJCWFkZChwW3BvXS55KTsKCQkJcG8gKys7CgkJfQoJCWludCBhbnMgPSBhc2sobCwgcik7CgkJaW50IGluZCA9IHEuaW5kOwoJCWFuc3dbaW5kXSArPSBxLnNnbiAqIGFuczsKCX0KCUZvcihpLDAscSkKCQlwcmludGYoIiVkXG4iLCBhbnN3W2ldICk7Cn0KCg==