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 maxn = 4e5 + 10;
const int maxq = 5e5 + 10;
char s[maxn];
vector<int> foo[maxn], linker[maxn];
int n, m, ch[maxn][26], len[maxn], fa[maxn], lst = 1, rt = 1, tot = 1,
                                             now_pos[maxn], ed[maxn];
int ls[maxn * 20], rs[maxn * 20], sum[maxn * 20], root[maxn], dfn[maxn],
    out[maxn];
void extend(int x, int now, int bel) {
  int p = lst;
  if (ch[p][x]) {
    int q = ch[p][x];
    if (len[q] == len[p] + 1)
      lst = q;
    else {
      int np = ++tot;
      memcpy(ch[np], ch[q], sizeof ch[q]);
      fa[np] = fa[q], fa[q] = np;
      len[np] = len[p] + 1;
      lst = np;
      for (; p && ch[p][x] == q; p = fa[p]) ch[p][x] = np;
    }
  } else {
    int np = ++tot;
    len[np] = len[p] + 1;
    lst = np;
    for (; p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
    if (!p)
      fa[np] = rt;
    else {
      int q = ch[p][x];
      if (len[q] == len[p] + 1)
        fa[np] = q;
      else {
        int nq = ++tot;
        memcpy(ch[nq], ch[q], sizeof ch[q]);
        fa[nq] = fa[q], fa[q] = fa[np] = nq;
        len[nq] = len[p] + 1;
        for (; p && ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
      }
    }
  }
  now_pos[now] = lst;
  foo[lst].push_back(bel);
}
int ind = 0, seq[maxn];
void dfs(int x) {
  dfn[x] = ++ind;
  seq[ind] = x;
  for (int cur : linker[x]) dfs(cur);
  out[x] = ind;
}
int cnt = 0;
int insert(int y, int l, int r, int pos) {
  int x = ++cnt;
  sum[x] = sum[y] + 1;
  if (l == r) return x;
  int mid = (l + r) >> 1;
  ls[x] = ls[y], rs[x] = rs[y];
  if (pos <= mid)
    ls[x] = insert(ls[y], l, mid, pos);
  else
    rs[x] = insert(rs[y], mid + 1, r, pos);
  return x;
}
int query(int x, int y, int l, int r, int ql, int qr) {
  if (!x || sum[x] == sum[y]) return 0;
  if (l >= ql && r <= qr) return sum[x] - sum[y];
  int mid = (l + r) >> 1, res = 0;
  if (ql <= mid) res += query(ls[x], ls[y], l, mid, ql, qr);
  if (qr > mid) res += query(rs[x], rs[y], mid + 1, r, ql, qr);
  return res;
}
void build() {
  for (int i = 2; i <= tot; i++) linker[fa[i]].push_back(i);
  dfs(1);
  for (int i = 1; i <= ind; i++) {
    root[i] = root[i - 1];
    int now = seq[i];
    for (int cur : foo[now]) root[i] = insert(root[i], 1, n, cur);
  }
}
struct ask {
  int l, r, id;
  ask() {}
  ask(int l, int r, int id) : l(l), r(r), id(id) {}
};
vector<ask> bar[maxn];
int ans[maxq];
void get_ans(int x) {
  for (auto cur : bar[x]) {
    ans[cur.id] = query(root[out[x]], root[dfn[x] - 1], 1, n, cur.l, cur.r);
  }
  for (int cur : linker[x]) get_ans(cur);
}
int main() {
  int q;
  scanf("%d%d", &n, &q), m = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    lst = rt;
    ed[i - 1] = m;
    for (int j = 1; j <= len; j++) {
      extend(s[j] - 'a', ++m, i);
    }
  }
  ed[n] = m;
  build();
  for (int i = 1; i <= q; i++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    bar[now_pos[ed[k]]].push_back(ask(l, r, i));
  }
  get_ans(1);
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}