Problem: What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercase English letters. What is double strange that a phone number can be associated with several bears!

In that country there is a rock band called CF consisting of n bears (including Mike) numbered from 1 to n. 

<image>

Phone number of i-th member of CF is si. May 17th is a holiday named Phone Calls day. In the last Phone Calls day, everyone called all the numbers that are substrings of his/her number (one may call some number several times). In particular, everyone called himself (that was really strange country).

Denote as call(i, j) the number of times that i-th member of CF called the j-th member of CF. 

The geek Mike has q questions that he wants to ask you. In each question he gives you numbers l, r and k and you should tell him the number 

<image>

Input

The first line of input contains integers n and q (1 ≤ n ≤ 2 × 105 and 1 ≤ q ≤ 5 × 105).

The next n lines contain the phone numbers, i-th line contains a string si consisting of lowercase English letters (<image>).

The next q lines contain the information about the questions, each of them contains integers l, r and k (1 ≤ l ≤ r ≤ n and 1 ≤ k ≤ n).

Output

Print the answer for each question in a separate line.

Examples

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5


Output

7
5
6
3
6

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
inline int Add(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
inline int Sub(int x) { return x < 0 ? x + mod : x; }
inline void Sub(int &x, int y) { x = Sub(x - y); }
inline int Mul(int x, int y) { return (int)((unsigned long long)x * y % mod); }
inline int Mul(int x, int y, int z) {
  return (int)((unsigned long long)x * y % mod * z % mod);
}
int Pow(int x, int y) {
  int z = 1;
  for (; y; y >>= 1) {
    if (y & 1) z = Mul(z, x);
    x = Mul(x, x);
  }
  return z;
}
int Inv(int x) { return Pow(x, mod - 2); }
template <class T>
inline void Max(T &x, T y) {
  if (y > x) x = y;
}
template <class T>
inline void Min(T &x, T y) {
  if (y < x) x = y;
}
const int maxn = 2e5, maxq = 5e5;
int ans[maxq];
namespace tree {
const int maxn = 4e5;
int n;
int a[maxn];
void Init(int width) { n = width; }
int Low(int i) { return i & -i; }
void Add(int i, int x) {
  for (; i < n; i += Low(i + 1)) a[i] += x;
}
int Sum(int i) {
  int s = 0;
  for (; i >= 0; i -= Low(i + 1)) s += a[i];
  return s;
}
int Query(int l, int r) { return Sum(r - 1) - Sum(l - 1); }
}  // namespace tree
namespace sam {
const int maxnd = 8e5;
const int maxc = 27;
int nd, last;
struct Node {
  int par, len, tran[maxc];
  int right;
} node[maxnd];
void Clear(int u) {
  node[u] = {-1, 0, {}, -1};
  memset((node[u].tran), (-1), sizeof(node[u].tran));
}
void Init(void) {
  nd = 1;
  last = 0;
  Clear(0);
}
void Append(int c, int id) {
  int u = last;
  last = nd++;
  Clear(last);
  node[last].len = node[u].len + 1;
  node[last].right = id;
  for (; u != -1 && node[u].tran[c] == -1; u = node[u].par) {
    node[u].tran[c] = last;
  }
  if (u == -1) {
    node[last].par = 0;
  } else if (node[node[u].tran[c]].len == node[u].len + 1) {
    node[last].par = node[u].tran[c];
  } else {
    int v = node[u].tran[c], v2 = nd++;
    node[v2] = node[v];
    node[v2].len = node[u].len + 1;
    node[v2].right = -1;
    node[v].par = node[last].par = v2;
    for (; u != -1 && node[u].tran[c] == v; u = node[u].par) {
      node[u].tran[c] = v2;
    }
  }
}
struct Query {
  int l, r, id;
};
vector<int> g[maxnd];
vector<Query> qry[maxnd];
void Dfs(int u) {
  for (Query q : qry[u]) {
    ans[q.id] -= tree::Query(q.l, q.r);
  }
  if (node[u].right != -1) {
    tree::Add(node[u].right, 1);
  }
  for (int v : g[u]) {
    Dfs(v);
  }
  for (Query q : qry[u]) {
    ans[q.id] += tree::Query(q.l, q.r);
  }
}
void Solve(void) {
  for (int i = 0; i < nd; ++i) {
    g[i].clear();
  }
  for (int i = 1; i < nd; ++i) {
    g[node[i].par].push_back(i);
  }
  Dfs(0);
}
int GetRoot(const char *s, int n) {
  int u = 0;
  for (int i = 0; i < n; ++i) {
    int c = s[i] - 'a';
    u = node[u].tran[c];
  }
  return u;
}
}  // namespace sam
int n, q;
char str[maxn * 2 + 1];
int head[maxn + 1];
int root[maxn];
int main(void) {
  scanf("%d%d", &n, &q);
  head[0] = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%s", str + head[i]);
    int len = (int)strlen(str + head[i]);
    str[head[i] + len] = '#';
    head[i + 1] = head[i] + len + 1;
  }
  tree::Init(head[n]);
  sam::Init();
  for (int i = 0; i < head[n]; ++i) {
    int c = str[i] == '#' ? 26 : str[i] - 'a';
    sam::Append(c, i);
  }
  for (int i = 0; i < n; ++i) {
    root[i] = sam::GetRoot(str + head[i], head[i + 1] - head[i] - 1);
  }
  for (int i = 0; i < q; ++i) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    --l, --k;
    sam::qry[root[k]].push_back({head[l], head[r], i});
  }
  sam::Solve();
  for (int i = 0; i < q; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}