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 = 555555;
const int M = 888888;
const int MOD = 1e9 + 7;
const int intINF = 1e9;
const long long llINF = 2e18;
const double pi = acos(-1.0);
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double eps = 1e-10;
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
long long readll() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
unsigned long long readull() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
char s[N];
vector<pair<int, int> > V[N];
int n, m;
void predo() {}
int nxt[N][26], pos[N], fa[N], cnt, len;
void build(int k) {
  int u = 1;
  for (int i = (int)1; i <= (int)len; i++) {
    int c = s[i] - 'a';
    if (!nxt[u][c]) nxt[u][c] = ++cnt, fa[cnt] = u;
    u = nxt[u][c];
  }
  pos[k] = u;
}
void init() {
  n = read(), m = read();
  cnt = 1;
  for (int i = (int)1; i <= (int)n; i++) {
    scanf("%s", s + 1);
    len = strlen(s + 1);
    build(i);
  }
  for (int i = (int)1; i <= (int)m; i++) {
    int l = read(), r = read(), k = read();
    V[l - 1].push_back(make_pair(k, -i));
    V[r].push_back(make_pair(k, i));
  }
}
int q[N], fail[N];
void acauto() {
  int t = 0, w = 1;
  q[1] = 1;
  while (t < w) {
    int u = q[++t];
    for (int i = (int)0; i <= (int)25; i++) {
      if (nxt[u][i]) {
        int son = nxt[u][i], p = fail[u];
        if (u == 1)
          fail[son] = 1;
        else
          fail[son] = nxt[p][i];
        q[++w] = son;
      } else {
        int p = fail[u];
        if (u == 1)
          nxt[u][i] = 1;
        else
          nxt[u][i] = nxt[p][i];
      }
    }
  }
}
vector<int> G[N];
int st[N], sz[N], tim;
void dfs(int u) {
  st[u] = ++tim;
  sz[u] = 1;
  for (auto v : G[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}
int t[N << 2];
void pushup(int p) { t[p] = t[p << 1] + t[p << 1 | 1]; }
void update(int l, int r, int x, int y, int p) {
  if (l == r) {
    t[p] += y;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(l, mid, x, y, p << 1);
  else
    update(mid + 1, r, x, y, p << 1 | 1);
  pushup(p);
}
int query(int l, int r, int x, int y, int p) {
  if (x <= l && r <= y) return t[p];
  int mid = (l + r) >> 1;
  int res = 0;
  if (x <= mid) res += query(l, mid, x, y, p << 1);
  if (y > mid) res += query(mid + 1, r, x, y, p << 1 | 1);
  return res;
}
int ans[N];
void solve() {
  acauto();
  for (int i = (int)2; i <= (int)cnt; i++) G[fail[i]].push_back(i);
  dfs(1);
  for (int i = (int)1; i <= (int)n; i++) {
    int p = pos[i];
    while (p != 1) {
      update(1, tim, st[p], 1, 1);
      p = fa[p];
    }
    for (auto t : V[i]) {
      int u = t.first;
      int l = st[pos[u]], r = st[pos[u]] + sz[pos[u]] - 1;
      int res = query(1, tim, l, r, 1);
      if (t.second > 0)
        ans[t.second] += res;
      else
        ans[-t.second] -= res;
    }
  }
  for (int i = (int)1; i <= (int)m; i++) printf("%d\n", ans[i]);
}
int main() {
  predo();
  int cas = 1;
  while (cas--) {
    init();
    solve();
  }
  return 0;
}