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:200000')
using namespace std;
template <typename T>
class SparseTable {
 private:
  vector<vector<T> > spt;
  int SIZE, n;

 public:
  SparseTable(){};
  SparseTable(vector<T> v) {
    n = v.size();
    spt.resize(n);
    SIZE = log2(n) + 2;
    for (int i = 0; i < n; ++i) {
      spt[i].resize(SIZE);
      spt[i][0] = v[i];
    }
    for (int j = 1; j < SIZE; ++j) {
      for (int i = 0; i + (1 << (j - 1)) < n; ++i) {
        spt[i][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  T queryRange(int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    return min(spt[l][lg], spt[r - (1 << lg) + 1][lg]);
  }
};
int n, t;
int p[500005], r[500005], h[500005];
string s;
void fix_index(int *b, int *e) {
  int pkm1, pk, np, i, d, m;
  pkm1 = p[*b + t];
  m = e - b;
  d = 0;
  np = b - r;
  for (i = 0; i < m; i++) {
    if (((pk = p[*b + t]) != pkm1) && !(np <= pkm1 && pk < np + m)) {
      pkm1 = pk;
      d = i;
    }
    p[*(b++)] = np + d;
  }
}
bool comp(int i, int j) { return p[i + t] < p[j + t]; }
void suff_arr() {
  int i, j, bc[256];
  t = 1;
  for (i = 0; i < 256; i++) bc[i] = 0;
  for (i = 0; i < n; i++) ++bc[int(s[i])];
  for (i = 1; i < 256; i++) bc[i] += bc[i - 1];
  for (i = 0; i < n; i++) r[--bc[int(s[i])]] = i;
  for (i = n - 1; i >= 0; i--) p[i] = bc[int(s[i])];
  for (t = 1; t < n; t *= 2) {
    for (i = 0, j = 1; i < n; i = j++) {
      while (j < n && p[r[j]] == p[r[i]]) ++j;
      if (j - i > 1) {
        sort(r + i, r + j, comp);
        fix_index(r + i, r + j);
      }
    }
  }
}
void lcp() {
  int tam = 0, i, j;
  for (i = 0; i < n; i++)
    if (p[i] > 0) {
      j = r[p[i] - 1];
      while (s[i + tam] == s[j + tam]) ++tam;
      h[p[i] - 1] = tam;
      if (tam > 0) --tam;
    }
  h[n - 1] = 0;
}
const int N = (int)5e5;
struct Node {
  int v, L, R;
  Node(){};
  Node(int _v, int _L, int _R) {
    v = _v;
    L = _L;
    R = _R;
  }
};
Node st[N * 20];
int root[N], nc = 1;
int update(int no, int l, int r, int i) {
  int NO = nc++;
  st[NO] = st[no];
  st[NO].v++;
  if (l == r) return NO;
  int md = (l + r) >> 1;
  if (i <= md)
    st[NO].L = update(st[NO].L, l, md, i);
  else
    st[NO].R = update(st[NO].R, md + 1, r, i);
  return NO;
}
int query(int nol, int nor, int l, int r, int i, int j) {
  if (r < i || l > j) return 0;
  if (l >= i && r <= j) return st[nor].v - st[nol].v;
  int md = (l + r) >> 1;
  return query(st[nol].L, st[nor].L, l, md, i, j) +
         query(st[nol].R, st[nor].R, md + 1, r, i, j);
}
int m, q;
char str[N];
int start[N], idx[N], sz[N];
inline pair<int, int> getBounds(int k, SparseTable<int> &bt) {
  int lo = 0, hi = p[start[k]];
  while (lo < hi) {
    int md = (lo + hi) >> 1;
    if (bt.queryRange(md, p[start[k]] - 1) >= sz[k])
      hi = md;
    else
      lo = md + 1;
  }
  int a = lo;
  lo = p[start[k]], hi = n - 1;
  while (lo < hi) {
    int md = (lo + hi) >> 1;
    if (bt.queryRange(p[start[k]], md) >= sz[k])
      lo = md + 1;
    else
      hi = md;
  }
  int b = lo;
  return make_pair(a, b);
}
int main() {
  scanf("%d %d", &m, &q);
  for (int i = 1; i <= m; ++i) {
    scanf(" %s", str);
    start[i] = s.size();
    int l = strlen(str);
    sz[i] = l;
    for (int j = 0; j < l; ++j) s.push_back(str[j]);
    s.push_back('$');
  };
  n = s.size();
  suff_arr();
  for (int i = 0; i < n; ++i) {
    idx[p[i]] = upper_bound(start + 1, start + m + 1, i) - start - 1;
  }
  for (int i = 0; i < n; ++i) {
    ;
  };
  lcp();
  for (int i = 0; i < n; ++i) {
    ;
    root[i + 1] = update(root[i], 1, m, idx[i + 1]);
  };
  SparseTable<int> lcpMin(vector<int>(h, h + n));
  while (q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    pair<int, int> sol = getBounds(k, lcpMin);
    int a = sol.first, b = sol.second;
    printf("%d\n", query(root[a - 1], root[b], 1, m, l, r));
  }
  return 0;
}