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 inf = 0x3f3f3f3f;
const int Maxn = 5e5 + 5;
const int N = 4e5 + 5;
const int M = 26;
int read() {
  int s = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s * f;
}
char s[N];
long long Ans[Maxn];
vector<int> G[N];
int n, m, pos[N], Len[N], Root[N], p[N][20];
struct Tree {
  int l, r;
  long long sum;
};
struct Segment_Tree {
  int tot;
  Tree t[N * 20];
  void Update(int x, int &p, int l, int r) {
    if (!p) p = ++tot;
    t[p].sum++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) Update(x, t[p].l, l, mid);
    if (x > mid) Update(x, t[p].r, mid + 1, r);
  }
  int Merge(int x, int y) {
    if (!x || !y) return x | y;
    t[x].sum += t[y].sum;
    t[x].l = Merge(t[x].l, t[y].l);
    t[x].r = Merge(t[x].r, t[y].r);
    return x;
  }
  long long Query(int x, int y, int p, int l, int r) {
    if (y < l || x > r || !p) return 0;
    if (x <= l && r <= y) return t[p].sum;
    int mid = (l + r) >> 1;
    return Query(x, y, t[p].l, l, mid) + Query(x, y, t[p].r, mid + 1, r);
  }
} tree;
struct SAM {
  int tot = 1, lst = 1, root = 1;
  int fa[N], ch[N][M], len[N];
  void Insert(int num, int id) {
    int x = lst, fx = ++tot;
    len[fx] = len[x] + 1;
    while (x && !ch[x][num]) {
      ch[x][num] = fx;
      x = fa[x];
    }
    if (!x)
      fa[fx] = root;
    else {
      int y = ch[x][num];
      if (len[y] == len[x] + 1)
        fa[fx] = y;
      else {
        int fy = ++tot;
        len[fy] = len[x] + 1;
        fa[fy] = fa[y];
        fa[y] = fa[fx] = fy;
        memcpy(ch[fy], ch[y], sizeof(ch[fy]));
        while (x && ch[x][num] == y) {
          ch[x][num] = fy;
          x = fa[x];
        }
      }
    }
    lst = fx;
    tree.Update(id, Root[lst], 1, n);
  }
  void Build() {
    for (int i = 2; i <= tot; i++) G[fa[i]].push_back(i);
    for (int i = 1; i <= tot; i++) p[i][0] = fa[i];
    for (int j = 1; j < 20; j++) {
      for (int i = 1; i <= tot; i++) p[i][j] = p[p[i][j - 1]][j - 1];
    }
  }
} sam;
struct Node {
  int l, r, id;
};
vector<Node> Q[N];
void DFS(int x) {
  for (auto y : G[x]) {
    DFS(y);
    Root[x] = tree.Merge(Root[x], Root[y]);
  }
  for (auto F : Q[x]) Ans[F.id] = tree.Query(F.l, F.r, Root[x], 1, n);
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    sam.lst = 1;
    for (int j = 1; j <= len; j++) sam.Insert(s[j] - 'a', i);
    pos[i] = sam.lst;
    Len[i] = len;
  }
  sam.Build();
  for (int i = 1; i <= n; i++) {
    for (int j = 19; j >= 0; j--) {
      if (sam.len[p[pos[i]][j]] >= Len[i]) pos[i] = p[pos[i]][j];
    }
  }
  for (int i = 1; i <= m; i++) {
    int l = read(), r = read(), k = read();
    Q[pos[k]].push_back((Node){l, r, i});
  }
  DFS(1);
  for (int i = 1; i <= m; i++) printf("%lld\n", Ans[i]);
  return 0;
}