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;
namespace SGT {
int ls[8000005], rs[8000005], tot;
long long sm[8000005];
void add(int &k, int l, int r, int p) {
  if (!k) k = ++tot;
  sm[k]++;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (p <= mid)
    add(ls[k], l, mid, p);
  else
    add(rs[k], mid + 1, r, p);
}
int merge(int x, int y, int l, int r) {
  if (!x || !y) return x | y;
  int k = ++tot, mid = (l + r) >> 1;
  sm[k] = sm[x] + sm[y];
  if (l != r)
    ls[k] = merge(ls[x], ls[y], l, mid),
    rs[k] = merge(rs[x], rs[y], mid + 1, r);
  return k;
}
long long qry(int k, int l, int r, int x, int y) {
  if (!k) return 0;
  if (x <= l && r <= y) return sm[k];
  int mid = (l + r) >> 1;
  if (y <= mid) return qry(ls[k], l, mid, x, y);
  if (x > mid) return qry(rs[k], mid + 1, r, x, y);
  return qry(ls[k], l, mid, x, y) + qry(rs[k], mid + 1, r, x, y);
}
}  // namespace SGT
int rt[400005];
char po[200005], *s[200005];
int ed[200005], lcs[200005], le[200005];
int tot = 1, len[400005], fat[400005], son[400005][26], n, m, l;
inline int insert(int lst, int x, vector<int> id) {
  int p = lst, q, k, u = ++tot;
  len[u] = len[p] + 1;
  for (int asd : id) SGT::add(rt[u], 1, n, asd);
  while (p && !son[p][x]) son[p][x] = u, p = fat[p];
  if (!p) {
    fat[u] = 1;
    return u;
  }
  if (len[p] + 1 == len[q = son[p][x]]) {
    fat[u] = q;
    return u;
  }
  len[k = ++tot] = len[p] + 1;
  fat[k] = fat[q];
  fat[u] = fat[q] = k;
  memcpy(son[k], son[q], sizeof(son[q]));
  while (p && son[p][x] == q) son[p][x] = k, p = fat[p];
  return u;
}
vector<int> e[400005];
int ch[200005][26], lst[200005], sz = 1;
vector<int> id[200005];
void ins(char *S, int T) {
  for (int i = 0, u = 1, c; S[i];
       le[T]++, u = ch[u][c], id[u].push_back(T), i++)
    if (!ch[u][c = S[i] - 'a']) ch[u][c] = ++sz;
}
void dfs(int u) {
  for (int i = 0; i < 26; i++)
    if (ch[u][i])
      lst[ch[u][i]] = insert(lst[u], i, id[ch[u][i]]), dfs(ch[u][i]);
}
void DFS(int u) {
  for (int v : e[u]) DFS(v), rt[u] = SGT::merge(rt[u], rt[v], 1, n);
}
int main() {
  scanf("%d%d", &n, &m);
  s[0] = po;
  for (int i = 1; i <= n; i++)
    s[i] = s[i - 1] + le[i - 1], scanf("%s", s[i]), ins(s[i], i);
  lst[1] = 1;
  dfs(1);
  for (int i = 2; i <= tot; i++) e[fat[i]].emplace_back(i);
  DFS(1);
  for (int T = 1; T <= n; T++) {
    int u = 1, L = 0;
    for (int i = 0; i < le[T]; i++) {
      while (u && !son[u][s[T][i] - 'a']) u = fat[u], L = len[u];
      if (!u)
        u = 1, L = 0;
      else
        u = son[u][s[T][i] - 'a'], L++;
    }
    lcs[T] = L;
    ed[T] = u;
  }
  for (int l, r, k; m--;) {
    scanf("%d%d%d", &l, &r, &k);
    printf("%lld\n", SGT::qry(rt[ed[k]], 1, n, l, r));
  }
}