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>
namespace ZDY {
#pragma GCC optimize(3)
template <class T>
__inline__ __attribute__((always_inline)) T ABS(T x) {
  return x > 0 ? x : -x;
}
template <class T>
__inline__ __attribute__((always_inline)) T MAX(T x, T y) {
  return x > y ? x : y;
}
template <class T>
__inline__ __attribute__((always_inline)) T MIN(T x, T y) {
  return x < y ? x : y;
}
template <class T>
__inline__ __attribute__((always_inline)) T GCD(T x, T y) {
  return y ? GCD(y, x % y) : x;
}
template <class T>
__inline__ __attribute__((always_inline)) void SWAP(T &x, T &y) {
  T t = x;
  x = y;
  y = t;
}
}  // namespace ZDY
using namespace ZDY;
using namespace std;
namespace IO {
const int str = 1 << 20;
static char in_buf[str], *in_s, *in_t;
bool __ = 0;
__inline__ __attribute__((always_inline)) char gc() {
  return (in_s == in_t) &&
             (in_t = (in_s = in_buf) + fread(in_buf, 1, str, stdin)),
         in_s == in_t ? EOF : *in_s++;
}
__inline__ __attribute__((always_inline)) void in(string &ch) {
  ch.clear();
  if (__) return;
  char c;
  while ((c = gc()) != EOF && isspace(c))
    ;
  if (c == EOF) {
    __ = 1;
    return;
  }
  ch += c;
  while ((c = gc()) != EOF && !isspace(c)) ch += c;
  if (c == EOF) __ = 1;
}
__inline__ __attribute__((always_inline)) void in(char &ch) {
  if (__) return;
  char c;
  while ((c = gc()) != EOF && isspace(c))
    ;
  if (c == EOF)
    __ = 1;
  else
    ch = c;
}
__inline__ __attribute__((always_inline)) void in(char *ch) {
  *ch = '\0';
  if (__) return;
  char c;
  while ((c = gc()) != EOF && isspace(c))
    ;
  if (c == EOF) {
    __ = 1;
    return;
  }
  *ch = c;
  ch++;
  while ((c = gc()) != EOF && !isspace(c)) *ch = c, ch++;
  if (c == EOF) __ = 1;
  *ch = '\0';
}
template <typename T>
__inline__ __attribute__((always_inline)) void in(T &x) {
  if (__) return;
  char c = gc();
  bool f = 0;
  while (c != EOF && (c < '0' || c > '9')) f ^= (c == '-'), c = gc();
  if (c == EOF) {
    __ = 1;
    return;
  }
  x = 0;
  while (c != EOF && '0' <= c && c <= '9') x = x * 10 + c - 48, c = gc();
  if (c == EOF) __ = 1;
  if (f) x = -x;
}
template <typename T, typename... arr>
__inline__ __attribute__((always_inline)) void in(T &x, arr &...y) {
  in(x), in(y...);
}
const char ln = '\n';
static char out_buf[str], *out_s = out_buf, *out_t = out_buf + str;
__inline__ __attribute__((always_inline)) void flush() {
  fwrite(out_buf, 1, out_s - out_buf, stdout);
  out_s = out_buf;
}
__inline__ __attribute__((always_inline)) void pt(char c) {
  (out_s == out_t) ? (fwrite(out_s = out_buf, 1, str, stdout), *out_s++ = c)
                   : (*out_s++ = c);
}
__inline__ __attribute__((always_inline)) void out(const char *s) {
  while (*s) pt(*s++);
}
__inline__ __attribute__((always_inline)) void out(char *s) {
  while (*s) pt(*s++);
}
__inline__ __attribute__((always_inline)) void out(char c) { pt(c); }
__inline__ __attribute__((always_inline)) void out(string s) {
  for (int i = 0; s[i]; i++) pt(s[i]);
}
template <typename T>
__inline__ __attribute__((always_inline)) void out(T x) {
  if (!x) {
    pt('0');
    return;
  }
  if (x < 0) pt('-'), x = -x;
  char a[50], t = 0;
  while (x) a[t++] = x % 10, x /= 10;
  while (t--) pt(a[t] + '0');
}
template <typename T, typename... arr>
__inline__ __attribute__((always_inline)) void out(T x, arr &...y) {
  out(x), out(y...);
}
}  // namespace IO
using namespace IO;
const int N = 200011, M = 500011;
int n, m, cnt = 0, head[N], k[M], ans[M];
char ch[N];
struct edge {
  int to, nxt;
} e[N * 26];
__inline__ __attribute__((always_inline)) void add(int x, int y) {
  e[++cnt].to = y;
  e[cnt].nxt = head[x];
  head[x] = cnt;
}
int tot = 1, tr[N][26], ed[N], f[N], fail[N], q[N * 26];
__inline__ __attribute__((always_inline)) void build() {
  int h = 0, t = 0, x;
  for (int i(0); i <= 25; ++i)
    if (tr[1][i])
      fail[tr[1][i]] = 1, q[t++] = tr[1][i];
    else
      tr[1][i] = 1;
  while (h < t) {
    x = q[h++];
    for (int i(0); i <= 25; ++i)
      if (tr[x][i])
        fail[tr[x][i]] = tr[fail[x]][i], q[t++] = tr[x][i];
      else
        tr[x][i] = tr[fail[x]][i];
  }
}
int id[N], sz = 0, siz[N];
void dfs(int x) {
  id[x] = ++sz;
  siz[x] = 1;
  for (int i(head[x]), to; to = e[i].to, i; i = e[i].nxt)
    dfs(to), siz[x] += siz[to];
}
int s[N];
__inline__ __attribute__((always_inline)) void upd(int x) {
  for (int i = x; i <= tot; i += i & -i) ++s[i];
}
__inline__ __attribute__((always_inline)) int ask(int x) {
  int t = 0;
  for (int i = x; i; i -= i & -i) t += s[i];
  return t;
}
int main() {
  in(n, m);
  for (int i(1); i <= n; ++i) {
    in(ch);
    int p = 1, len = strlen(ch), c;
    for (int j(0); j <= len - 1; ++j) {
      c = ch[j] - 'a';
      if (!tr[p][c]) f[tr[p][c] = ++tot] = p;
      p = tr[p][c];
    }
    ed[i] = p;
  }
  build();
  for (int i(2); i <= tot; ++i) add(fail[i], i);
  dfs(1);
  memset(head, 0, sizeof(head));
  cnt = 0;
  int l, r, x;
  for (int i(1); i <= m; ++i) {
    in(l, r, k[i]);
    if (l > 1) add(l - 1, -i);
    add(r, i);
  }
  for (int i(1); i <= n; ++i) {
    for (x = ed[i]; x != 1; x = f[x]) upd(id[x]);
    for (int j(head[i]), to; to = e[j].to, j; j = e[j].nxt) {
      int v = to > 0 ? 1 : -1;
      to *= v;
      x = ed[k[to]];
      ans[to] += v * (ask(id[x] + siz[x] - 1) - ask(id[x] - 1));
    }
  }
  for (int i(1); i <= m; ++i) out(ans[i], ln);
  flush();
}