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;
struct st {
  int l, r, ori;
} P[500005];
int n, q;
int a, b, c, x;
int sz[500005], lcp[500005], rnk[500005], D[20][500005], T[500005][20],
    B[500005], ans[500005], LG[500005];
char s[500005];
string S;
vector<pair<pair<int, int>, int> > L[500005], R[500005];
bool cmp(st a, st b) {
  if (a.l == b.l) return a.r < b.r;
  return a.l < b.l;
}
void suffix() {
  x = S.length();
  for (int i = 0; i <= x - 1; i++) D[0][i] = (S[i] == '#' ? 26 : S[i] - 'a');
  for (int i = 1, k = 1; (1 << i) <= x; i++, k *= 2) {
    for (int h = 0; h <= x - 1; h++) {
      P[h].l = D[i - 1][h];
      P[h].r = (h + k < x ? D[i - 1][h + k] : -1);
      P[h].ori = h;
    }
    sort(P, P + x, cmp);
    for (int h = 1, r = 0; h < x; h++) {
      if (P[h].l != P[h - 1].l || P[h].r != P[h - 1].r) r++;
      D[i][P[h].ori] = r;
    }
  }
  int lg = log2(x);
  for (int i = 1; i <= x - 1; i++) {
    int a = P[i - 1].ori;
    int b = P[i].ori;
    for (int h = lg; h >= 0; h--)
      if (a < x && b < x && D[h][a] == D[h][b])
        lcp[i] += (1 << h), a += (1 << h), b += (1 << h);
  }
}
int Min(int l, int r) {
  int lg = LG[r - l + 1];
  return min(T[l][lg], T[r - (1 << lg) + 1][lg]);
}
void upd(int a) {
  for (; a <= x; a += a & -a) B[a]++;
}
int get(int a) {
  int ret = 0;
  for (; a > 0; a -= a & -a) ret += B[a];
  return ret;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    sz[i] = strlen(s);
    for (int h = 0; h <= sz[i] - 1; h++) S += s[h];
    sz[i] += sz[i - 1];
    if (i != n) S += '#';
  }
  for (int a = 0, b = 1, i = 1; i < 500005 - 5; i++) {
    if (b * 2 > i)
      LG[i] = a;
    else
      a++, b *= 2, LG[i] = a;
  }
  suffix();
  x = S.length();
  for (int i = 0; i <= x - 1; i++) rnk[P[i].ori + 1] = i + 1;
  for (int i = 1; i <= x; i++) T[i][0] = lcp[i - 1];
  for (int h = 1; (1 << h) <= x; h++)
    for (int i = 1; i <= x && i + (1 << (h - 1)) <= x; i++)
      T[i][h] = min(T[i][h - 1], T[i + (1 << (h - 1))][h - 1]);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d%d", &a, &b, &c);
    int l = 0, r = rnk[sz[c - 1] + c], len = sz[c] - sz[c - 1], p = r + 1;
    for (int i = 18; i >= 0; i--)
      if (l + (1 << i) <= r && Min(r - (l + (1 << i)) + 1, r) >= len)
        l += (1 << i);
    l = r - l;
    for (int i = 18; i >= 0; i--)
      if (r + (1 << i) <= x && Min(p, r + (1 << i)) >= len) r += (1 << i);
    L[l].push_back({{sz[b] + b - 1, sz[a - 1] + a}, i});
    R[r].push_back({{sz[b] + b - 1, sz[a - 1] + a}, i});
  }
  for (int i = 1; i <= x; i++) {
    for (auto h : L[i])
      ans[h.second] -= get(h.first.first) - get(h.first.second - 1);
    upd(P[i - 1].ori + 1);
    for (auto h : R[i])
      ans[h.second] += get(h.first.first) - get(h.first.second - 1);
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}