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;
struct SuffixArray {
  vector<int> lcp;
  vector<vector<pair<int, int> > > rmq;
  int n, h;
  vector<int> sa, invsa;
  bool cmp(int a, int b) { return invsa[a + h] < invsa[b + h]; }
  void ternary_sort(int a, int b) {
    if (a == b) return;
    int pivot = sa[a + rand() % (b - a)];
    int left = a, right = b;
    for (int i = a; i < b; ++i)
      if (cmp(sa[i], pivot)) swap(sa[i], sa[left++]);
    for (int i = b - 1; i >= left; --i)
      if (cmp(pivot, sa[i])) swap(sa[i], sa[--right]);
    ternary_sort(a, left);
    for (int i = left; i < right; ++i) invsa[sa[i]] = right - 1;
    if (right - left == 1) sa[left] = -1;
    ternary_sort(right, b);
  }
  SuffixArray() {}
  SuffixArray(vector<int> v) : n(v.size()), sa(n) {
    v.push_back(INT_MIN);
    invsa = v;
    iota(sa.begin(), sa.end(), 0);
    h = 0;
    ternary_sort(0, n);
    for (h = 1; h <= n; h *= 2) {
      for (int j = 0, i = j; i != n; i = j) {
        if (sa[i] < 0) {
          while (j < n && sa[j] < 0) j += -sa[j];
          sa[i] = -(j - i);
        } else {
          j = invsa[sa[i]] + 1;
          ternary_sort(i, j);
        }
      }
    }
    for (int i = 0; i < n; ++i) sa[invsa[i]] = i;
    lcp.resize(n);
    int res = 0;
    for (int i = 0; i < n; ++i) {
      if (invsa[i] > 0)
        while (v[i + res] == v[sa[invsa[i] - 1] + res]) ++res;
      lcp[invsa[i]] = res;
      res = max(res - 1, 0);
    }
    int logn = 0;
    while ((1 << logn + 1) <= n) ++logn;
    rmq.resize(logn + 1, vector<pair<int, int> >(n));
    for (int i = 0; i < n; ++i) rmq[0][i] = make_pair(lcp[i], i);
    for (int l = 1; l <= logn; ++l)
      for (int i = 0; i + (1 << l) <= n; ++i)
        rmq[l][i] = min(rmq[l - 1][i], rmq[l - 1][i + (1 << l - 1)]);
  }
  pair<int, int> rmq_query(int a, int b) {
    int size = b - a + 1, l = 31 - __builtin_clz(size);
    return min(rmq[l][a], rmq[l][b - (1 << l) + 1]);
  }
  int get_lcp2(int ia, int ib) {
    return rmq_query(min(ia, ib) + 1, max(ia, ib)).first;
  }
  pair<int, int> get_range(int strpos, int size) {
    int pos = invsa[strpos];
    int start, end;
    {
      int l = 0, r = pos;
      while (l < r) {
        int m = (l + r) / 2;
        if (get_lcp2(m, pos) < size)
          l = m + 1;
        else
          r = m;
      }
      start = l;
    }
    {
      int l = pos, r = n - 1;
      while (l < r) {
        int m = (l + r + 1) / 2;
        if (get_lcp2(m, pos) < size)
          r = m - 1;
        else
          l = m;
      }
      end = l;
    }
    return {start, end};
  }
};
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 n, m, q;
char str[N];
int start[N], idx[N], sz[N];
vector<int> s;
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] - 'a');
    s.push_back(INT_MIN);
  }
  SuffixArray sa(s);
  n = s.size();
  for (int i = 0; i < n; ++i) {
    idx[sa.invsa[i]] = upper_bound(start + 1, start + m + 1, i) - start - 1;
  }
  for (int i = m - 1; i < n; ++i) {
    root[i + 1] = update(root[i], 1, m, idx[i + 1]);
  }
  while (q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    pair<int, int> sol = sa.get_range(start[k], sz[k]);
    int a = sol.first, b = sol.second;
    printf("%d\n", query(root[a - 1], root[b], 1, m, l, r));
  }
  return 0;
}