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;
inline void read(int &x) {
  x = 0;
  int ch = getchar();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  x = x * sign;
}
const int maxn = 200010;
const int maxm = 400010;
const int maxq = 500010;
char S[maxm];
int SL[maxn], SR[maxn];
int Sa[maxm], tmpx[maxm], tmpy[maxm];
int Rank[maxm];
int c[maxm];
void BuildSA(int n, int m) {
  register int i, k, *x = tmpx, *y = tmpy;
  for (i = 0; i < m; i++) c[i] = 0;
  for (i = 0; i < n; i++) c[x[i] = (S[i] - 'a' + 1)]++;
  for (i = 1; i < m; i++) c[i] += c[i - 1];
  for (i = n - 1; i >= 0; i--) Sa[--c[x[i]]] = i;
  for (k = 1; k <= n; k <<= 1) {
    int p = 0;
    for (i = n - k; i < n; i++) y[p++] = i;
    for (i = 0; i < n; i++)
      if (Sa[i] >= k) y[p++] = Sa[i] - k;
    for (i = 0; i < m; i++) c[i] = 0;
    for (i = 0; i < n; i++) c[x[y[i]]]++;
    for (i = 1; i < m; i++) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--) Sa[--c[x[y[i]]]] = y[i];
    swap(x, y);
    p = 1;
    x[Sa[0]] = 0;
    for (i = 1; i < n; i++)
      x[Sa[i]] = y[Sa[i - 1]] == y[Sa[i]] && y[Sa[i - 1] + k] == y[Sa[i] + k]
                     ? p - 1
                     : p++;
    if (p >= n) break;
    m = p;
  }
  for (int i = 0; i < n; i++) Rank[Sa[i]] = i;
}
int n, m, q;
inline int find(int L, int R, char c, int len) {
  L--;
  R++;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (S[Sa[mid] + len - 1] < c)
      L = mid;
    else
      R = mid;
  }
  return R;
}
int PL[maxn], PR[maxn];
int ql[maxq], qr[maxq], qk[maxq];
vector<int> Q[maxn];
int Ans[maxq];
int T[maxm];
inline void Change(int x, int v) {
  for (; x <= m; x += x & -x) T[x] += v;
}
inline int Calc(int x) {
  int Ans = 0;
  for (; x; x -= x & -x) Ans += T[x];
  return Ans;
}
int main() {
  read(n), read(q);
  m = 0;
  S[0] = 'a' - 1;
  for (int i = 1; i <= n; i++) {
    SL[i] = m + 1;
    scanf("%s", S + m + 1);
    m += strlen(S + m + 1);
    SR[i] = m;
    if (i < n) S[++m] = 'z' + 1;
  }
  BuildSA(m + 1, 28);
  for (int i = 1; i <= n; i++) {
    int &L = PL[i], &R = PR[i];
    L = 1;
    R = m;
    for (int j = SL[i]; j <= SR[i]; j++) {
      int l = find(L, R, S[j], j - SL[i] + 1);
      int r = find(L, R, S[j] + 1, j - SL[i] + 1) - 1;
      L = l;
      R = r;
    }
  }
  for (int i = 1; i <= q; i++) {
    read(ql[i]), read(qr[i]), read(qk[i]);
    Q[qr[i]].push_back(i);
    Q[ql[i] - 1].push_back(-i);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = SL[i]; j <= SR[i]; j++) Change(Rank[j], 1);
    for (int j = 0; j < (int)Q[i].size(); j++) {
      int id = abs(Q[i][j]);
      int Sum = Calc(PR[qk[id]]) - Calc(PL[qk[id]] - 1);
      Ans[id] += Sum * (id == Q[i][j] ? 1 : -1);
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", Ans[i]);
  return 0;
}