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;
int fail[400010], sn[400010][30], nxt = 0, N, fa[400010], H;
vector<int> bel[400010];
int laster[400010], root[4000010], root_mark[400010];
char rd[200010];
queue<int> qu;
int qxx[400010][2], tt[400010], nn;
void add(int u, int v) {
  qxx[++nn][0] = v;
  qxx[nn][1] = tt[u];
  tt[u] = nn;
}
int c[4000010][2], sm[4000010], Q;
int bul_emp(int L, int R) {
  if (L == R) return 0;
  int M = (L + R) >> 1;
  int rt = ++Q;
  c[rt][0] = bul_emp(L, M);
  c[rt][1] = bul_emp(M + 1, R);
  return rt;
}
int mdf(int O, int L, int R, int P) {
  int rt = ++Q;
  c[rt][0] = c[O][0];
  c[rt][1] = c[O][1];
  sm[rt] = sm[O] + 1;
  if (L == R) return rt;
  int M = (L + R) >> 1;
  if (P <= M)
    c[rt][0] = mdf(c[O][0], L, M, P);
  else
    c[rt][1] = mdf(c[O][1], M + 1, R, P);
  return rt;
}
int in[400010], out[400010], idx;
void dfs(int u) {
  in[u] = ++idx;
  for (int i = tt[u]; i; i = qxx[i][1]) {
    int v = qxx[i][0];
    dfs(v);
  }
  out[u] = idx;
}
int query(int R1, int R2, int L, int R, int l, int r) {
  if (l <= L && R <= r) return sm[R1] - sm[R2];
  int M = (L + R) >> 1;
  if (r <= M) return query(c[R1][0], c[R2][0], L, M, l, r);
  if (l > M) return query(c[R1][1], c[R2][1], M + 1, R, l, r);
  return query(c[R1][0], c[R2][0], L, M, l, r) +
         query(c[R1][1], c[R2][1], M + 1, R, l, r);
}
int main() {
  scanf("%d%d", &N, &H);
  for (int i = 1; i <= N; i++) {
    scanf(" %s", rd);
    int now = 0;
    for (int j = 0; rd[j]; j++) {
      if (sn[now][rd[j] - 'a'] == 0) {
        ++nxt;
        sn[now][rd[j] - 'a'] = nxt;
        fa[nxt] = now;
      }
      now = sn[now][rd[j] - 'a'];
      bel[now].push_back(j);
      rd[j] = '\0';
    }
    laster[i] = now;
  }
  for (int i = 0; i < 26; i++)
    if (sn[0][i]) qu.push(sn[0][i]);
  while (!qu.empty()) {
    int x = qu.front();
    qu.pop();
    for (int i = 0; i < 26; i++) {
      if (sn[x][i]) {
        fail[sn[x][i]] = sn[fail[x]][i];
        qu.push(sn[x][i]);
      } else
        sn[x][i] = sn[fail[x]][i];
    }
  }
  for (int i = 1; i <= nxt; i++) add(fail[i], i);
  dfs(0);
  int cnt = 0;
  root[0] = bul_emp(1, idx);
  for (int i = 1; i <= N; i++) {
    for (int j = laster[i]; j; j = fa[j]) {
      ++cnt;
      root[cnt] = mdf(root[cnt - 1], 1, idx, in[j]);
    }
    root_mark[i] = root[cnt];
  }
  while (H--) {
    int al, ar, ak;
    scanf("%d%d%d", &al, &ar, &ak);
    printf("%d\n", query(root_mark[ar], root_mark[al - 1], 1, idx,
                         in[laster[ak]], out[laster[ak]]));
  }
  return 0;
}