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 N = 800010;
const int K = 21;
char s[N], ch[N];
int n, m, len[N], head[N], tot;
int tmp[N], top[N], rk[N], sa[N], lcp[N];
void makesa(int n) {
  int i, j, k;
  for (i = 0; i < n; i++) top[rk[i] = s[i]]++;
  for (i = 1; i < 128; i++) top[i] += top[i - 1];
  for (i = 0; i < n; i++) sa[--top[rk[i]]] = i;
  for (k = 1; k <= n; k <<= 1) {
    for (i = 0; i < n; i++) {
      j = sa[i] - k;
      if (j < 0) j += n;
      tmp[top[rk[j]]++] = j;
    }
    sa[tmp[top[0] = 0]] = j = 0;
    for (int i = 1; i < n; i++) {
      if (rk[tmp[i]] != rk[tmp[i - 1]] || rk[tmp[i] + k] != rk[tmp[i - 1] + k])
        top[++j] = i;
      sa[tmp[i]] = j;
    }
    memcpy(rk, sa, n * sizeof(int));
    memcpy(sa, tmp, n * sizeof(int));
    if (j >= n - 1) break;
  }
  for (j = rk[lcp[i = k = 0] = 0]; i < n - 1; i++, k++)
    while (k >= 0 && s[i] != s[sa[j - 1] + k]) {
      lcp[j] = k--;
      j = rk[sa[j] + 1];
    }
}
int st[N][K], g[K];
void makest(int n) {
  int i, j, k, t;
  t = (int)log2(n);
  for (i = g[0] = 1; i <= t; i++) g[i] = g[i - 1] << 1;
  for (i = 0; i <= n; i++) st[i][0] = lcp[i];
  for (k = 1; k <= t; k++)
    for (i = 0; i <= n; i++)
      if (i + g[k - 1] > n)
        st[i][k] = st[i][k - 1];
      else
        st[i][k] = min(st[i][k - 1], st[i + g[k - 1]][k - 1]);
}
int getlcp(int x, int y) {
  x++;
  int t = (int)log2(y - x + 1);
  return min(st[x][t], st[y - g[t] + 1][t]);
}
const int M = 10000010;
int root[N], son[M][2], data[M], cnt;
int add(int i, int l, int r, int x, int y) {
  int t = ++cnt, mid = (l + r) >> 1;
  data[t] = data[i] + y;
  if (l == r) return t;
  if (x <= mid)
    son[t][0] = add(son[i][0], l, mid, x, y), son[t][1] = son[i][1];
  else
    son[t][1] = add(son[i][1], mid + 1, r, x, y), son[t][0] = son[i][0];
  return t;
}
int ask(int i, int j, int l, int r, int x, int y) {
  if (!i) return data[j];
  if (x <= l && y >= r) return data[j] - data[i];
  int mid = (l + r) >> 1, ans = 0;
  if (x <= mid) ans += ask(son[i][0], son[j][0], l, mid, x, y);
  if (y > mid) ans += ask(son[i][1], son[j][1], mid + 1, r, x, y);
  return ans;
}
int checkl(int l, int r, int x, int y) {
  int t = x;
  while (l <= r) {
    int mid = (l + r) >> 1;
    int tmp = getlcp(mid, x);
    if (tmp >= y)
      r = (t = mid) - 1;
    else
      l = mid + 1;
  }
  return t;
}
int checkr(int l, int r, int x, int y) {
  int t = x;
  while (l <= r) {
    int mid = (l + r) >> 1;
    int tmp = getlcp(x, mid);
    if (tmp >= y)
      l = (t = mid) + 1;
    else
      r = mid - 1;
  }
  return t;
}
int main() {
  int l, r, x;
  scanf("%d%d\n", &n, &m);
  for (int i = 1; i <= n; i++) {
    gets(ch);
    head[i] = tot;
    len[i] = strlen(ch);
    for (int j = 0; j < len[i]; j++) s[tot++] = ch[j];
    s[tot++] = '$';
  }
  head[n + 1] = tot;
  makesa(tot + 1);
  n = tot;
  makest(n);
  for (int i = 1; i <= n; i++) root[i] = add(root[i - 1], 0, n, sa[i], 1);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &l, &r, &x);
    int pos = rk[head[x]];
    int tx = checkl(1, pos - 1, pos, len[x]);
    int ty = checkr(pos + 1, tot, pos, len[x]);
    printf("%d\n", ask(root[tx - 1], root[ty], 0, n, head[l], head[r + 1] - 1));
  }
  return 0;
}