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;
template <typename T>
inline int chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline int chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline T read() {
  T sum = 0, fl = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fl = -1;
  for (; isdigit(ch); ch = getchar())
    sum = (sum << 3) + (sum << 1) + (ch - '0');
  return sum * fl;
}
const int maxn = 2e5 + 5;
const int maxm = 5e5 + 5;
int fin[maxn];
namespace TRIE {
struct Node {
  int ch[26];
  int c, fa, pos;
  Node() {
    memset(ch, 0, sizeof ch);
    pos = fa = c = 0;
  }
} o[maxn];
}  // namespace TRIE
namespace SAM {
const int maxn = ::maxn << 1;
struct Node {
  int ch[26];
  int fa, maxlen;
  Node() {
    fa = maxlen = 0;
    memset(ch, 0, sizeof ch);
  }
} o[maxn];
int node_cnt = 1;
inline int insert(int c, int lst) {
  int now = ++node_cnt, pre = lst;
  o[now].maxlen = o[pre].maxlen + 1;
  for (; pre && !o[pre].ch[c]; pre = o[pre].fa) o[pre].ch[c] = now;
  if (pre == 0)
    o[now].fa = 1;
  else {
    int first = o[pre].ch[c];
    if (o[pre].maxlen + 1 == o[first].maxlen)
      o[now].fa = first;
    else {
      int second = ++node_cnt;
      o[second] = o[first];
      o[second].maxlen = o[pre].maxlen + 1;
      o[first].fa = o[now].fa = second;
      for (; pre && o[pre].ch[c] == first; pre = o[pre].fa)
        o[pre].ch[c] = second;
    }
  }
  return now;
}
inline int query(string S, int p = 1) {
  for (int i = 0, M = S.length(); i < M; ++i) p = o[p].ch[S[i] - 'a'];
  return p;
}
}  // namespace SAM
int N, M;
string S[maxn];
inline void sam_build() {
  using namespace TRIE;
  int node_cnt = 1;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0, p = 1, M = S[i].length(); j < M; ++j) {
      int &to = o[p].ch[S[i][j] - 'a'];
      if (to == 0) to = ++node_cnt, o[to].c = S[i][j] - 'a', o[to].fa = p;
      p = to;
      fin[i] = p;
    }
  }
  static queue<int> Q;
  for (int i = 0; i <= 25; ++i)
    if (o[1].ch[i]) Q.push(o[1].ch[i]);
  o[1].pos = 1;
  while (!Q.empty()) {
    int p = Q.front();
    Q.pop();
    o[p].pos = SAM ::insert(o[p].c, o[o[p].fa].pos);
    for (int i = 0; i <= 25; ++i)
      if (TRIE ::o[p].ch[i]) Q.push(TRIE ::o[p].ch[i]);
  }
}
namespace SEG {
struct Node {
  int ch[2];
  long long cnt;
  Node() {
    ch[0] = ch[1] = 0;
    cnt = 0;
  }
} o[maxn * 40];
int node_cnt;
inline void pushup(int rt) {
  o[rt].cnt = o[(o[rt].ch[0])].cnt + o[(o[rt].ch[1])].cnt;
}
void update(int &rt, int l, int r, int p) {
  if (!rt) rt = ++node_cnt;
  if (l == r) {
    ++o[rt].cnt;
    return;
  }
  if (p <= ((l + r) >> 1))
    update((o[rt].ch[0]), l, ((l + r) >> 1), p);
  else
    update((o[rt].ch[1]), ((l + r) >> 1) + 1, r, p);
  pushup(rt);
}
int merge(int p, int q, int l, int r) {
  if (!p || !q) return p | q;
  int rt = ++node_cnt;
  if (l == r) {
    o[rt].cnt = o[p].cnt + o[q].cnt;
    return rt;
  }
  (o[rt].ch[0]) = merge(o[p].ch[0], o[q].ch[0], l, ((l + r) >> 1));
  (o[rt].ch[1]) = merge(o[p].ch[1], o[q].ch[1], ((l + r) >> 1) + 1, r);
  pushup(rt);
  return rt;
}
long long query(int rt, int l, int r, int ql, int qr) {
  if (!rt) return 0;
  if (l >= ql && r <= qr) return o[rt].cnt;
  long long sum = 0;
  if (ql <= ((l + r) >> 1))
    sum = query((o[rt].ch[0]), l, ((l + r) >> 1), ql, qr);
  if (qr > ((l + r) >> 1))
    sum += query((o[rt].ch[1]), ((l + r) >> 1) + 1, r, ql, qr);
  return sum;
}
}  // namespace SEG
int rt[maxn << 1];
vector<int> E[maxn << 1];
void dfs(int fa, int p) {
  for (int i = 0; i < E[p].size(); ++i) dfs(p, E[p][i]);
  if (fa) rt[fa] = SEG ::merge(rt[fa], rt[p], 1, N);
}
inline void tree_build() {
  for (int i = 1; i <= N; ++i) {
    for (int j = 0, p = 1, M = S[i].length(); j < M; ++j) {
      p = TRIE ::o[p].ch[S[i][j] - 'a'];
      SEG ::update(rt[TRIE ::o[p].pos], 1, N, i);
    }
  }
  for (int i = 1; i <= SAM ::node_cnt; ++i) E[SAM ::o[i].fa].push_back(i);
  dfs(0, 1);
}
struct Query {
  int k, l, r;
} q[maxm];
vector<int> vec[maxn];
long long Ans[maxm];
inline void solve() {
  sam_build();
  tree_build();
  for (int i = 1; i <= N; ++i) {
    int pos = SAM ::query(S[i]);
    for (int j = 0; j < vec[i].size(); ++j) {
      int id = vec[i][j];
      Ans[id] = SEG ::query(rt[pos], 1, N, q[id].l, q[id].r);
    }
  }
  for (int i = 1; i <= M; ++i) printf("%lld\n", Ans[i]);
}
inline void input() {
  N = read<int>();
  M = read<int>();
  for (int i = 1; i <= N; ++i) cin >> S[i];
  for (int i = 1; i <= M; ++i) {
    q[i].l = read<int>(), q[i].r = read<int>();
    q[i].k = read<int>();
    vec[q[i].k].push_back(i);
  }
}
int main() {
  input();
  solve();
  return 0;
}