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;
template <typename T, typename U>
inline void chkmax(T &x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
inline void chkmin(T &x, U y) {
  if (y < x) x = y;
}
const int MAXN = 444444;
char s[MAXN], t[MAXN];
int wa[MAXN], wb[MAXN], wc[MAXN], wd[MAXN];
int sa[MAXN], rnk[MAXN], d[19][MAXN];
namespace SA {
bool is_equal(int *r, int a, int b, int l, int n) {
  int la = r[a], lb = r[b], ra, rb;
  ra = a + l < n ? r[a + l] : -1;
  rb = b + l < n ? r[b + l] : -1;
  return (la == lb) && (ra == rb);
}
void buildSA(char *r, int *sa, int n, int m) {
  int *x = wa, *y = wb;
  memset(wc, 0, sizeof(int) * m);
  for (int i = 0; i < n; i++) wc[x[i] = r[i]]++;
  for (int i = 1; i < m; i++) wc[i] += wc[i - 1];
  for (int i = n - 1; i >= 0; i--) sa[--wc[x[i]]] = i;
  for (int tot = 0, p = 1; tot + 1 < n; p <<= 1, m = tot + 1) {
    tot = 0;
    for (int i = n - p; i < n; i++) y[tot++] = i;
    for (int i = 0; i < n; i++)
      if (sa[i] >= p) y[tot++] = sa[i] - p;
    for (int i = 0; i < n; i++) wd[i] = x[y[i]];
    memset(wc, 0, sizeof(int) * m);
    for (int i = 0; i < n; i++) wc[wd[i]]++;
    for (int i = 1; i < m; i++) wc[i] += wc[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--wc[wd[i]]] = y[i];
    swap(x, y);
    x[sa[0]] = tot = 0;
    for (int i = 1; i < n; i++)
      x[sa[i]] = is_equal(y, sa[i - 1], sa[i], p, n) ? tot : ++tot;
  }
}
void buildLCP(char *r, int *sa, int *lcp, int n) {
  for (int i = 0; i < n; i++) rnk[sa[i]] = i;
  lcp[0] = 0;
  for (int i = 0; i < n; i++)
    if (rnk[i]) {
      lcp[rnk[i]] = ((i == 0) ? 0 : max(0, lcp[rnk[i - 1]] - 1));
      for (; r[i + lcp[rnk[i]]] == r[sa[rnk[i] - 1] + lcp[rnk[i]]];
           lcp[rnk[i]]++)
        ;
    }
}
};  // namespace SA
vector<int> V[MAXN];
int n, m, q;
int st[MAXN], en[MAXN], dp[MAXN], who[MAXN], L[MAXN], R[MAXN], l[555555],
    r[555555], ans[555555];
void add(int x) {
  for (; x <= n; x += x & -x) dp[x]++;
}
int get(int x) {
  int ret = 0;
  for (; x; x -= x & -x) ret += dp[x];
  return ret;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%s", t);
    st[i] = m;
    for (int j = 0; t[j]; j++) who[m] = i, s[m++] = t[j];
    en[i] = m;
    if (i < n) s[m++] = 'z' + 1;
  }
  SA::buildSA(s, sa, m, 128);
  SA::buildLCP(s, sa, d[0], m);
  for (int i = 1; i <= 18; i++) {
    for (int j = 0; j < m; j++) {
      d[i][j] = d[i - 1][j];
      if (j + (1 << (i - 1)) < m) chkmin(d[i][j], d[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int i = 1; i <= n; i++) {
    int j = st[i], l = en[i] - st[i];
    L[i] = rnk[j], R[i] = rnk[j];
    for (int k = 18; k >= 0; k--) {
      if (L[i] >= (1 << (k)) - 1 && d[k][L[i] - (1 << (k)) + 1] >= l)
        L[i] -= (1 << (k));
      if (R[i] + (1 << (k)) < m && d[k][R[i] + 1] >= l) R[i] += (1 << (k));
    }
  }
  for (int i = 1; i <= q; i++) {
    int k;
    scanf("%d%d%d", &l[i], &r[i], &k);
    if (L[k] > 0) V[L[k] - 1].push_back(-i);
    V[R[k]].push_back(i);
  }
  for (int i = 0; i < m; i++) {
    if (!who[sa[i]]) break;
    add(who[sa[i]]);
    for (int j = 0; j < V[i].size(); j++) {
      int k = V[i][j];
      if (k > 0)
        ans[k] += get(r[k]) - get(l[k] - 1);
      else
        ans[-k] -= get(r[-k]) - get(l[-k] - 1);
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}