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 MAXL = 4e5 + 5, MAXQ = 5e5 + 5, MAXT = 8e6 + 5;
template <typename _T>
void read(_T &x) {
  x = 0;
  char s = getchar();
  int f = 1;
  while (s > '9' || s < '0') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') {
    x = (x << 3) + (x << 1) + (s - '0'), s = getchar();
  }
  x *= f;
}
template <typename _T>
void write(_T x) {
  if (x < 0) {
    putchar('-');
    x = (~x) + 1;
  }
  if (9 < x) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
struct Query {
  int l, r;
} q[MAXQ];
struct edge {
  int to, nxt;
} Graph[MAXL << 1];
vector<int> qs[MAXL], ep[MAXL];
int s[MAXT], lch[MAXT], rch[MAXT];
int ans[MAXQ];
int ch[MAXL][26], mx[MAXL], fa[MAXL], head[MAXL], rot[MAXL];
int ed[MAXL];
int N, Q, rt, lst, tot, cnt, siz;
char S[MAXL];
void upt(const int x) { s[x] = s[lch[x]] + s[rch[x]]; }
void copy(int a, int b) {
  fa[a] = fa[b], mx[a] = mx[b], memcpy(ch[a], ch[b], sizeof ch[b]);
}
void addEdge(const int from, const int to) {
  Graph[++cnt].to = to, Graph[cnt].nxt = head[from];
  head[from] = cnt;
}
void expand(const char c) {
  int x = c - 'a';
  if (ch[lst][x] && mx[ch[lst][x]] == mx[lst] + 1) {
    lst = ch[lst][x];
    return;
  }
  int p = lst, cur = ++tot;
  mx[cur] = mx[lst] + 1, lst = cur;
  while (p && !ch[p][x]) ch[p][x] = cur, p = fa[p];
  if (!p) {
    fa[cur] = rt;
    return;
  }
  int q = ch[p][x];
  if (mx[q] == mx[p] + 1) {
    fa[cur] = q;
    return;
  }
  int nq = ++tot;
  copy(nq, q);
  mx[nq] = mx[p] + 1, fa[q] = fa[cur] = nq;
  if (mx[p] + 1 == mx[cur]) lst = nq;
  while (p && ch[p][x] == q) ch[p][x] = nq, p = fa[p];
}
int update(const int u, const int l, const int r, const int pos) {
  int cur = u ? u : ++siz, mid = l + r >> 1;
  if (l == r) {
    s[cur]++;
    return cur;
  }
  if (pos <= mid)
    lch[cur] = update(lch[u], l, mid, pos);
  else
    rch[cur] = update(rch[u], mid + 1, r, pos);
  upt(cur);
  return cur;
}
int query(const int u, const int l, const int r, const int segL,
          const int segR) {
  if (!u) return 0;
  if (segL <= l && r <= segR) return s[u];
  if (l == r) return 0;
  int mid = l + r >> 1, ret = 0;
  if (segL <= mid) ret += query(lch[u], l, mid, segL, segR);
  if (mid < segR) ret += query(rch[u], mid + 1, r, segL, segR);
  return ret;
}
int merg(const int lrt, const int rrt) {
  if (!lrt || !rrt) return lrt + rrt;
  lch[lrt] = merg(lch[lrt], lch[rrt]);
  rch[lrt] = merg(rch[lrt], rch[rrt]);
  s[lrt] += s[rrt];
  return lrt;
}
void DFS(const int u) {
  rot[u] = 0;
  for (int i = head[u], v; i; i = Graph[i].nxt) {
    DFS(v = Graph[i].to);
    rot[u] = merg(rot[u], rot[v]);
  }
  for (int i = 0; i < ep[u].size(); i++)
    rot[u] = update(rot[u], 1, N, ep[u][i]);
  for (int i = 0, cur; i < qs[u].size(); i++) {
    cur = qs[u][i];
    ans[cur] = query(rot[u], 1, N, q[cur].l, q[cur].r);
  }
}
int main() {
  rt = ++tot;
  read(N), read(Q);
  for (int i = 1; i <= N; i++) {
    lst = rt;
    scanf("%s", S + 1);
    for (int j = 1; S[j]; j++) expand(S[j]), ep[lst].push_back(i);
    ed[i] = lst;
  }
  for (int i = 1, k; i <= Q; i++) {
    read(q[i].l), read(q[i].r), read(k);
    qs[ed[k]].push_back(i);
  }
  for (int i = 2; i <= tot; i++) addEdge(fa[i], i);
  DFS(1);
  for (int i = 1; i <= Q; i++) write(ans[i]), putchar('\n');
  return 0;
}