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 N = 501010;
const int qwq = N * 22;
const int inf = 0x3f3f3f3f;
int n, m;
int cnt = 1, last = 1, tot;
int wei[N];
char s[N];
vector<int> e[N];
int ch[N][26], fa[N], len[N];
int rt[N], tree[qwq], L[qwq], R[qwq];
struct Q {
  int id, x, y;
};
vector<Q> d[N];
int ans[N];
inline int read() {
  int lyy = 0, zbk = 1;
  char z7z = getchar();
  while (z7z < '0' || z7z > '9') {
    if (z7z == '-') zbk = -1;
    z7z = getchar();
  }
  while (z7z >= '0' && z7z <= '9') {
    lyy = lyy * 10 + z7z - '0';
    z7z = getchar();
  }
  return lyy * zbk;
}
void insert(int &u, int l, int r, int we) {
  u = ++tot;
  tree[u] = 1;
  if (l == r) return;
  int mid = l + r >> 1;
  if (we <= mid)
    insert(L[u], l, mid, we);
  else
    insert(R[u], mid + 1, r, we);
}
int merge(int u, int v, int l, int r) {
  if (!u || !v) return u | v;
  if (l == r) {
    tree[u] = tree[u] + tree[v];
    return u;
  }
  int mid = l + r >> 1;
  L[u] = merge(L[u], L[v], l, mid);
  R[u] = merge(R[u], R[v], mid + 1, r);
  tree[u] = tree[L[u]] + tree[R[u]];
  return u;
}
int query(int u, int l, int r, int x, int y) {
  if (!u) return 0;
  if (x <= l && r <= y) return tree[u];
  int mid = l + r >> 1, res = 0;
  if (x <= mid) res += query(L[u], l, mid, x, y);
  if (y > mid) res += query(R[u], mid + 1, r, x, y);
  return res;
}
inline void add(int c, int id) {
  int u = last;
  last = ++cnt;
  insert(rt[cnt], 1, n, id);
  len[cnt] = len[u] + 1;
  for (; u && !ch[u][c]; u = fa[u]) ch[u][c] = cnt;
  if (!u)
    fa[cnt] = 1;
  else {
    int zjt = ch[u][c];
    if (len[zjt] == len[u] + 1)
      fa[cnt] = zjt;
    else {
      int ob = cnt + 1;
      memcpy(ch[ob], ch[zjt], sizeof(ch[zjt]));
      fa[ob] = fa[zjt];
      len[ob] = len[u] + 1;
      fa[zjt] = fa[cnt] = ob;
      for (; u && ch[u][c] == zjt; u = fa[u]) ch[u][c] = ob;
      cnt++;
    }
  }
}
void DFS(int u) {
  for (int i = 0; i < e[u].size(); i++) {
    int v = e[u][i];
    DFS(v);
    rt[u] = merge(rt[u], rt[v], 1, n);
  }
  for (int i = 0; i < d[u].size(); i++) {
    int id = d[u][i].id, x = d[u][i].x, y = d[u][i].y;
    ans[id] = query(rt[u], 1, n, x, y);
  }
}
int main() {
  int x, y, z;
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    int le = strlen(s + 1);
    last = 1;
    for (int j = 1; j <= le; j++) add(s[j] - 'a', i);
    wei[i] = last;
    if (len[last] == len[fa[last]]) wei[i] = fa[last];
  }
  for (int i = 2; i <= cnt; i++) e[fa[i]].push_back(i);
  for (int i = 1; i <= m; i++) {
    x = read();
    y = read();
    z = read();
    d[wei[z]].push_back((Q){i, x, y});
  }
  DFS(1);
  for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
  return 0;
}