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 long long read() {
  long long x = 0;
  char ch = getchar();
  bool d = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') d = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return d ? x : -x;
}
inline unsigned long long rnd() {
  return ((unsigned long long)rand() << 30 ^ rand()) << 4 | rand() % 4;
}
const int N = 1e6 + 5;
char s[N];
int n, m, sa[N], rk[N], h[N], x[N], y[N], c[N];
bool cmp(int i, int j, int k) { return y[i] != y[j] | y[i + k] != y[j + k]; }
void init() {
  int n = strlen(s + 1), m = 27;
  for (int i = (int)(1); i <= (int)(n); i++) c[x[i] = s[i] - 'a' + 1]++;
  for (int i = (int)(1); i <= (int)(m); i++) c[i] += c[i - 1];
  for (int i = (int)(n); i >= (int)(1); i--) sa[c[x[i]]--] = i;
  for (int k = 1; k < n; k <<= 1) {
    int p = 0;
    for (int i = (int)(n - k + 1); i <= (int)(n); i++) y[++p] = i;
    for (int i = (int)(1); i <= (int)(n); i++)
      if (sa[i] > k) y[++p] = sa[i] - k;
    for (int i = (int)(1); i <= (int)(m); i++) c[i] = 0;
    for (int i = (int)(1); i <= (int)(n); i++) c[x[i]]++;
    for (int i = (int)(1); i <= (int)(m); i++) c[i] += c[i - 1];
    for (int i = (int)(n); i >= (int)(1); i--) sa[c[x[y[i]]]--] = y[i];
    swap(x, y);
    m = 1;
    x[sa[1]] = 1;
    for (int i = (int)(2); i <= (int)(n); i++)
      x[sa[i]] = (m += cmp(sa[i], sa[i - 1], k));
    if (m >= n) break;
  }
  for (int i = (int)(1); i <= (int)(n); i++) rk[sa[i]] = i;
  int k = 0;
  for (int i = (int)(1); i <= (int)(n); i++)
    if (rk[i] != 1) {
      int p1 = i, p2 = sa[rk[i] - 1];
      k -= (k != 0);
      for (; s[p1 + k] == s[p2 + k]; k++)
        ;
      h[rk[i]] = k;
    }
}
int ans[N], pos[N], mn[20][N], alb[N], b[N];
struct info {
  int pos, p, op, id;
  bool operator<(const info &rhs) const { return pos < rhs.pos; }
} q[N << 1];
int find(int l, int r) {
  int k = alb[r - l + 1];
  return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
char t[N];
void add(int x) {
  for (int i = x; i < N; i += (i & -i)) c[i]++;
}
int query(int x) {
  int res = 0;
  for (int i = x; i; i -= (i & -i)) res += c[i];
  return res;
}
int main() {
  int len = 0, n = read(), m = read();
  for (int i = (int)(1); i <= (int)(n); i++) {
    scanf("%s", t + 1);
    int k = strlen(t + 1);
    b[i] = k;
    if (len) s[++len] = 'z' + 1;
    pos[i] = len + 1;
    for (int j = (int)(1); j <= (int)(k); j++) s[++len] = t[j];
  }
  pos[n + 1] = len + 1;
  init();
  for (int i = (int)(2); i <= (int)(len); i++) mn[0][i] = h[i];
  for (int i = (int)(1); i <= (int)(19); i++) {
    for (int j = 1; j + (1 << i) - 1 <= len; j++) {
      mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << i - 1)]);
    }
  }
  for (int i = (int)(2); i <= (int)(len); i++) alb[i] = alb[i >> 1] + 1;
  int Q = 0;
  for (int i = (int)(1); i <= (int)(m); i++) {
    int L = read(), R = read(), x = read(), y = b[x];
    int l = 1, r = rk[pos[x]] - 1, mid, pl = rk[pos[x]];
    while (l <= r) {
      find((mid = l + r >> 1) + 1, rk[pos[x]]) >= y ? r = (pl = mid) - 1
                                                    : l = mid + 1;
    }
    l = rk[pos[x]] + 1;
    r = len;
    int pr = rk[pos[x]];
    while (l <= r) {
      find(rk[pos[x]] + 1, mid = l + r >> 1) >= y ? l = (pr = mid) + 1
                                                  : r = mid - 1;
    }
    q[++Q] = (info){pos[R + 1] - 1, pr, 1, i};
    if (pos[L] - 1) q[++Q] = (info){pos[L] - 1, pr, -1, i};
    q[++Q] = (info){pos[R + 1] - 1, pl - 1, -1, i};
    if (pos[L] - 1) q[++Q] = (info){pos[L] - 1, pl - 1, 1, i};
  }
  memset(c, 0, sizeof(c));
  sort(q + 1, q + Q + 1);
  int j = 1;
  for (int i = (int)(1); i <= (int)(len); i++) {
    add(rk[i]);
    while (j <= Q && q[j].pos == i) {
      ans[q[j].id] += q[j].op * query(q[j].p);
      j++;
    }
  }
  for (int i = (int)(1); i <= (int)(m); i++) printf("%d\n", ans[i]);
}