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;
int read_int() {
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') {
    c = getchar();
  }
  bool sign = 0;
  if (c == '-') {
    sign = 1;
    c = getchar();
  }
  int ret = 0;
  while (c >= '0' && c <= '9') {
    ret = 10 * ret + c - 48;
    c = getchar();
  }
  if (sign) return -ret;
  return ret;
}
const int MAXL = 130072 * 4;
int S[MAXL * 2], SA[MAXL * 2];
bool _iss[MAXL * 2];
int _p[MAXL * 2], _pb[MAXL * 2], cnt[MAXL], qe[MAXL];
inline void isort(int n, int *s, int *sa, bool *iss, int *p, int pc) {
  int a = 0, i;
  for (i = 0; i < n; i++) a = max(a, s[i]);
  a++;
  memset(cnt, 0, sizeof(int) * a);
  for (i = 0; i < n; i++) cnt[s[i]]++;
  qe[0] = cnt[0];
  for (i = 1; i < a; i++) qe[i] = qe[i - 1] + cnt[i];
  memset(sa, -1, sizeof(int) * n);
  for (i = pc - 1; i >= 0; i--) sa[--qe[s[p[i]]]] = p[i];
  qe[0] = 0;
  for (i = 1; i < a; i++) qe[i] = qe[i - 1] + cnt[i - 1];
  for (i = 0; i < n; i++)
    if (sa[i] > 0 && !iss[sa[i] - 1]) sa[qe[s[sa[i] - 1]]++] = sa[i] - 1;
  qe[0] = cnt[0];
  for (i = 1; i < a; i++) qe[i] = qe[i - 1] + cnt[i];
  for (i = n - 1; i >= 0; i--)
    if (sa[i] > 0 && iss[sa[i] - 1]) sa[--qe[s[sa[i] - 1]]] = sa[i] - 1;
}
inline bool eq(int *s, bool *iss, int *pp, int *pb, int pc, int x, int p) {
  if (pb[p] == pc - 1 || pb[x] == pc - 1 ||
      pp[pb[p] + 1] - p != pp[pb[x] + 1] - x)
    return 0;
  for (int j = 0; j <= pp[pb[p] + 1] - p; j++)
    if (s[j + p] != s[j + x] || iss[j + p] != iss[j + x]) return 0;
  return 1;
}
void suffixArray(int n, int a1 = 0) {
  int i;
  int *s = S + a1, *sa = SA + a1, *pp = _p + a1, *pb = _pb + a1;
  bool *iss = _iss + a1;
  iss[n - 1] = 1;
  for (i = n - 2; i >= 0; i--)
    iss[i] = s[i] < s[i + 1] || (s[i] == s[i + 1] && iss[i + 1]);
  int pc = 0;
  for (i = 1; i < n; i++)
    if (iss[i] && !iss[i - 1]) {
      pp[pc] = i;
      pb[i] = pc;
      pc++;
    }
  isort(n, s, sa, iss, pp, pc);
  int p = -1, c = -1;
  for (i = 0; i < n; i++) {
    int x = sa[i];
    if (x && iss[x] && !iss[x - 1]) {
      if (p == -1 || !eq(s, iss, pp, pb, pc, x, p)) c++;
      s[n + pb[x]] = c;
      p = x;
    }
  }
  if (c == pc - 1)
    for (i = 0; i < pc; i++) sa[n + s[n + i]] = i;
  else
    suffixArray(pc, a1 + n);
  for (i = 0; i < pc; i++) pb[i] = pp[sa[n + i]];
  isort(n, s, sa, iss, pb, pc);
}
int rk[MAXL], DA[MAXL];
void depthArray(int n) {
  int i, j;
  for (i = 0; i < n; i++) rk[SA[i]] = i;
  for (i = j = 0; i < n; i++) {
    if (!rk[i]) {
      j = 0;
    } else {
      if (j) j--;
      for (; S[i + j] == S[SA[rk[i] - 1] + j]; j++)
        ;
    }
    DA[rk[i]] = j;
  }
}
struct snode {
  int sum;
  void merge(snode &l, snode &r) { sum = l.sum + r.sum; }
};
template <class node>
class segtree {
  template <bool b>
  class param {};
  inline void spltdwn(int idx, param<true>) { splt(idx); }
  inline void splt(int idx) {
    idx >>= 1;
    if (idx > 0) splt(idx);
    tree[idx].split(tree[idx << 1], tree[(idx << 1) | 1]);
  }
  inline void spltdwn(int, param<false>){};
  inline void split(node &a, node &b, node &c, param<true>) {
    return a.split(b, c);
  }
  inline void split(node &, node &, node &, param<false>) {}
  template <typename t, void (t::*)(t &, t &)>
  class T {};
  template <typename t>
  static char test(T<t, &t::split> *) {
    return 0;
  }
  template <typename t>
  static long double test(...) {
    return 0;
  }
  int u, v;
  node query(int root, int left_range, int right_range) {
    if (u <= left_range && right_range <= v) return tree[root];
    int mid = (left_range + right_range) >> 1, l = root << 1, r = l | 1;
    if (has_split) split(tree[root], tree[l], tree[r], param<has_split>());
    node res;
    if (u >= mid)
      res = query(r, mid, right_range);
    else if (v <= mid)
      res = query(l, left_range, mid);
    else {
      node n1 = query(l, left_range, mid), n2 = query(r, mid, right_range);
      res.merge(n1, n2);
    }
    if (has_split) tree[root].merge(tree[l], tree[r]);
    return res;
  }
  template <void (*fn)(node &)>
  void local_update(int root, int left_range, int right_range) {
    if (u <= left_range && right_range <= v) {
      return fn(tree[root]);
    }
    int mid = (left_range + right_range) >> 1, l = root << 1, r = l | 1;
    if (has_split) split(tree[root], tree[l], tree[r], param<has_split>());
    if (v > mid) local_update<fn>(r, mid, right_range);
    if (u < mid) local_update<fn>(l, left_range, mid);
    tree[root].merge(tree[l], tree[r]);
  }
  void mrgup(int idx) {
    idx >>= 1;
    while (idx > 0)
      tree[idx].merge(tree[idx << 1], tree[(idx << 1) | 1]), idx >>= 1;
  }

 public:
  static bool const has_split = (sizeof(test<node>(0)) == sizeof(char));
  int N;
  int leftmost_leaf, rightmost_leaf;
  node *tree;
  node identity;
  segtree() { tree = 0; }
  ~segtree() {
    if (tree) delete[] tree;
  }
  void init(int n, const node a[], const node &identity) {
    if (tree) delete[] tree;
    this->identity = identity;
    N = 0;
    while ((1 << N) < n) N++;
    leftmost_leaf = 1 << N;
    rightmost_leaf = leftmost_leaf << 1;
    tree = new node[rightmost_leaf];
    for (int i = 0; i < n; i++) tree[i + leftmost_leaf] = a[i];
    for (int i = n + leftmost_leaf; i < rightmost_leaf; i++) tree[i] = identity;
    for (int i = leftmost_leaf - 1; i; i--)
      tree[i].merge(tree[i << 1], tree[(i << 1) | 1]);
  }
  node query(int u, int v) {
    this->u = u + leftmost_leaf;
    this->v = v + leftmost_leaf + 1;
    return query(1, leftmost_leaf, rightmost_leaf);
  }
  node query(int u) {
    u += leftmost_leaf;
    spltdwn(u, param<has_split>());
    return tree[u];
  }
  template <void (*fn)(node &)>
  void update(int u, int v) {
    this->u = u + leftmost_leaf;
    this->v = v + leftmost_leaf + 1;
    return local_update<fn>(1, leftmost_leaf, rightmost_leaf);
  }
  template <void (*fn)(node &)>
  void update(int u) {
    u += leftmost_leaf;
    spltdwn(u, param<has_split>());
    fn(tree[u]);
    mrgup(u);
  }
  void split_down(int leaf_idx) {
    spltdwn(leaf_idx + leftmost_leaf, param<has_split>());
  }
  void merge_up(int leaf_idx) { mrgup(leaf_idx + leftmost_leaf); }
  bool is_leaf(int tree_idx) { return tree_idx >= leftmost_leaf; }
  int binary_search(node k) {
    int root = 1;
    node n = identity;
    assert(!(k < identity));
    while (!is_leaf(root)) {
      int left_child = root << 1, right_child = left_child | 1;
      if (has_split)
        split(tree[root], tree[left_child], tree[right_child],
              param<has_split>());
      node m;
      m.merge(n, tree[left_child]);
      if (m < k) {
        n = m;
        root = right_child;
      } else
        root = left_child;
    }
    node m;
    m.merge(n, tree[root]);
    mrgup(root);
    if (m < k)
      return root - leftmost_leaf;
    else
      return root - 1 - leftmost_leaf;
  }
};
int a1[500005], a2[500005];
int ans[500005];
vector<pair<int, int> > qu[500005];
int lows[500005], highs[500005];
snode sn2[500005];
segtree<snode> st2;
int mn[19][500005];
int lg[2 * 500005];
void upd(snode &cur) { cur.sum++; }
int rmq(int x, int y) {
  int p = lg[y - x + 1];
  return min(mn[p][x], mn[p][y - (1 << p) + 1]);
}
int main() {
  int n = read_int();
  int q = read_int();
  char c = getchar();
  int N = 0;
  for (int i = 0; i < n; i++) {
    while (c < 'a' || c > 'z') c = getchar();
    a1[i] = N;
    while (c >= 'a' && c <= 'z') {
      S[N] = c - 'a' + 1;
      c = getchar();
      N++;
    }
    a2[i] = N - 1;
    S[N] = 27;
    N++;
  }
  S[N] = 0;
  N++;
  suffixArray(N);
  depthArray(N);
  for (int i = 0; i < N; i++) {
    mn[0][i] = DA[i];
  }
  mn[0][N] = 0;
  for (int i = 0; i < 19; i++) {
    for (int j = (1 << i); j < 1 << (i + 1); j++) lg[j] = i;
  }
  for (int i = 1; (1 << i) <= N; i++) {
    for (int j = 0; j + (1 << i) <= N; j++) {
      mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int i = 0; i < q; i++) {
    int l = read_int() - 1;
    int r = read_int() - 1;
    int k = read_int() - 1;
    int len = a2[k] - a1[k] + 1;
    int p = rk[a1[k]];
    int low = p, high = p;
    int lo = p + 1, hi = N - 1;
    if (lo <= hi && rmq(p + 1, p + 1) >= len) {
      while (lo < hi) {
        int mi = (lo + hi) / 2 + 1;
        if (rmq(p + 1, mi) >= len) {
          lo = mi;
        } else
          hi = mi - 1;
      }
      high = lo;
    }
    lo = 0, hi = p - 1;
    if (lo <= hi && rmq(p, p) >= len) {
      while (lo < hi) {
        int mi = (lo + hi) / 2;
        if (rmq(mi + 1, p) >= len) {
          hi = mi;
        } else
          lo = mi + 1;
      }
      low = lo;
    }
    lows[i] = low;
    highs[i] = high;
    qu[a1[l]].push_back(make_pair(i, 1));
    qu[a2[r] + 1].push_back(make_pair(i, -1));
  }
  for (int i = 0; i < N; i++) {
    sn2[i].sum = 0;
  }
  sn2[N].sum = 0;
  st2.init(N, sn2, sn2[N]);
  for (int i = N - 1; i >= 0; i--) {
    st2.update<&upd>(rk[i]);
    for (int j = 0; j < qu[i].size(); j++) {
      ans[qu[i][j].first] +=
          qu[i][j].second *
          st2.query(lows[qu[i][j].first], highs[qu[i][j].first]).sum;
    }
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}