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>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
int wa[400100], wb[400100], wv[400100], wss[400100], sa[400100], r[400100];
inline int cmp(int *r, int a, int b, int l) {
  return r[a] == r[b] && r[a + l] == r[b + l];
}
inline void build_sa(int *r, int *s, int n, int m) {
  int i, j, p, *x = wa, *y = wb, *t;
  for (int i = 0; i < m; i++) wss[i] = 0;
  for (int i = 0; i < n; i++) wss[x[i] = r[i]] += 1;
  for (int i = 1; i < m; i++) wss[i] += wss[i - 1];
  for (int i = n - 1; i >= 0; i--) sa[--wss[x[i]]] = i;
  for (j = 1, p = 1; p < n; j *= 2, m = p) {
    for (p = 0, i = n - j; i < n; i++) y[p++] = i;
    for (int i = 0; i < n; i++)
      if (sa[i] >= j) y[p++] = sa[i] - j;
    for (int i = 0; i < n; i++) wv[i] = x[y[i]];
    for (int i = 0; i < m; i++) wss[i] = 0;
    for (int i = 0; i < n; i++) wss[wv[i]] += 1;
    for (int i = 0; i < m; i++) wss[i] += wss[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--wss[wv[i]]] = y[i];
    for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
  }
}
int ranking[400100], height[400100];
inline void build_height(int *r, int *s, int n) {
  int i, j, k = 0;
  for (int i = 1; i <= n; i++) ranking[sa[i]] = i;
  for (i = 0; i < n; height[ranking[i++]] = k) {
    for (k ? k-- : 0, j = sa[ranking[i] - 1]; r[i + k] == r[j + k]; k++)
      ;
  }
}
int logx[400100];
void Init_logx() {
  for (int i = 0; 1 << i < 400100; i++) logx[1 << i] = i;
  for (int i = 1; i < 400100; i++)
    if (!logx[i]) logx[i] = logx[i - 1];
}
int ST[400100][20];
void RMQ_Init(int n) {
  for (int i = 1; i <= n; i++) ST[i][0] = height[i];
  for (int j = 1; 1 << j <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      ST[i][j] = min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
    }
  }
}
inline int RMQ_Query(int l, int r) {
  int a = ranking[l], b = ranking[r];
  if (a > b) swap(a, b);
  a += 1;
  int k = logx[b - a + 1];
  return min(ST[a][k], ST[b - (1 << k) + 1][k]);
}
int n, q, lens, sta[200010], slens[200010];
char s[400100];
int findup(int ran, int len) {
  int l = 1, r = ran, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    int coml = RMQ_Query(sa[mid], sa[ran]);
    if (coml >= len)
      r = mid;
    else
      l = mid + 1;
  }
  return l;
}
int finddw(int ran, int len) {
  int l = ran, r = lens, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    mid++;
    int coml = RMQ_Query(sa[mid], sa[ran]);
    if (coml >= len)
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}
int lch[(200010 * 22)], rch[(200010 * 22)], val[(200010 * 22)], T[400100], nnod,
    bel[400100];
int plant(int l, int r) {
  int t = ++nnod;
  val[t] = 0;
  if (l == r) return t;
  int mid = (l + r) >> 1;
  lch[t] = plant(l, mid);
  rch[t] = plant(mid + 1, r);
  return t;
}
int update(int id, int p, int l, int r, int v) {
  int t = ++nnod;
  lch[t] = lch[id], rch[t] = rch[id], val[t] = val[id] + v;
  if (l == r) return t;
  int mid = (l + r) >> 1;
  if (p <= mid)
    lch[t] = update(lch[t], p, l, mid, v);
  else
    rch[t] = update(rch[t], p, mid + 1, r, v);
  return t;
}
int query(int lid, int rid, int ql, int qr, int l, int r) {
  if (ql == l && qr == r) return val[rid] - val[lid];
  int mid = (l + r) >> 1;
  if (qr <= mid)
    return query(lch[lid], lch[rid], ql, qr, l, mid);
  else if (mid < ql)
    return query(rch[lid], rch[rid], ql, qr, mid + 1, r);
  else
    return query(lch[lid], lch[rid], ql, mid, l, mid) +
           query(rch[lid], rch[rid], mid + 1, qr, mid + 1, r);
}
int main() {
  Init_logx();
  scanf("%d%d", &n, &q);
  lens = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + lens);
    slens[i] = (int)strlen(s + lens);
    lens += slens[i];
    s[lens++] = '#';
  }
  s[lens] = '\0';
  int tt = static_cast<int>('z');
  for (int i = 0; i <= lens; i++) {
    r[i] = static_cast<int>(s[i]);
    if (s[i] == '#') r[i] = ++tt;
  }
  build_sa(r, sa, lens + 1, tt + 1);
  build_height(r, sa, lens);
  RMQ_Init(lens);
  tt = 1;
  for (int i = 0; i < lens; i++) {
    if (i == 0 || s[i - 1] == '#') sta[tt++] = i;
  }
  tt = 1;
  for (int i = 0; i < lens; i++) {
    if (s[i] == '#')
      bel[i] = 0, tt++;
    else
      bel[i] = tt;
  }
  nnod = 0;
  T[0] = plant(1, n);
  for (int i = 1; i <= lens; i++) {
    if (s[sa[i]] == '#') continue;
    T[i] = update(T[i - 1], bel[sa[i]], 1, n, +1);
  }
  for (int iq = 1; iq <= q; iq++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    int ran = ranking[sta[k]];
    int up = findup(ran, slens[k]);
    int dw = finddw(ran, slens[k]);
    int ans = query(T[up - 1], T[dw], l, r, 1, n);
    printf("%d\n", ans);
  }
  return 0;
}