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;
template <typename T>
class wavelet {
  T L, R;
  vector<int> l;
  vector<T> sum;
  wavelet *lef, *rig;
  int r(int i) const { return i - l[i]; }

 public:
  template <typename ITER>
  wavelet(ITER bg, ITER en) {
    lef = rig = nullptr;
    L = *bg, R = *bg;
    for (auto it = bg; it != en; it++) L = min(L, *it), R = max(R, *it);
    if (L == R) return;
    T mid = L + (R - L) / 2;
    l.reserve(std::distance(bg, en) + 1);
    sum.reserve(std::distance(bg, en) + 1);
    l.push_back(0), sum.push_back(0);
    for (auto it = bg; it != en; it++)
      l.push_back(l.back() + (*it <= mid)), sum.push_back(sum.back() + *it);
    auto tmp = stable_partition(bg, en, [mid](T x) { return x <= mid; });
    if (bg != tmp) lef = new wavelet(bg, tmp);
    if (tmp != en) rig = new wavelet(tmp, en);
  }
  ~wavelet() {
    delete lef;
    delete rig;
  }
  T kth(int i, int j, int k) const {
    if (L >= R) return L;
    int c = l[j] - l[i - 1];
    if (c >= k)
      return lef->kth(l[i - 1] + 1, l[j], k);
    else
      return rig->kth(r(i - 1) + 1, r(j), k - c);
  }
  int cnt(int i, int j, T x) const {
    if (L > x) return j - i + 1;
    if (R <= x || L == R) return 0;
    int ans = 0;
    if (lef) ans += lef->cnt(l[i - 1] + 1, l[j], x);
    if (rig) ans += rig->cnt(r(i - 1) + 1, r(j), x);
    return ans;
  }
  T sumk(int i, int j, T k) {
    if (L == R) return R <= k ? L * (j - i + 1) : 0;
    if (R <= k) return sum[j] - sum[i - 1];
    int ans = 0;
    if (lef) ans += lef->sumk(l[i - 1] + 1, l[j], k);
    if (rig) ans += rig->sumk(r(i - 1) + 1, r(j), k);
    return ans;
  }
};
const int N = 400005;
int lcp[N], c[N];
void build_sa(char s[], int n, int a[]) {
  const int A = 300;
  int c1[n], a1[n], h[n + A];
  memset(h, 0, sizeof h);
  for (int i = 0; i < n; i++) {
    c[i] = s[i];
    h[c[i] + 1]++;
  }
  partial_sum(h, h + A, h);
  for (int i = 0; i < n; i++) a[h[c[i]]++] = i;
  for (int i = 0; i < n; i++) h[c[i]]--;
  for (int L = 1; L < n; L <<= 1) {
    for (int i = 0; i < n; i++) {
      int j = (a[i] - L + n) % n;
      a1[h[c[j]]++] = j;
    }
    int cc = -1;
    for (int i = 0; i < n; i++) {
      if (i == 0 || c[a1[i]] != c[a1[i - 1]] ||
          c[(a1[i] + L) % n] != c[(a1[i - 1] + L) % n])
        h[++cc] = i;
      c1[a1[i]] = cc;
    }
    memcpy(a, a1, sizeof a1);
    memcpy(c, c1, sizeof c1);
    if (cc == n - 1) break;
  }
}
void build_lcp(char s[], int n, int a[]) {
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (c[i] == n - 1) continue;
    int j = a[c[i] + 1];
    while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
    lcp[c[i]] = k;
    if (k) k--;
  }
}
int dn[N][20];
int fn(int i, int j) {
  if (j == 0) return lcp[i];
  if (~dn[i][j]) return dn[i][j];
  return dn[i][j] = min(fn(i, j - 1), fn(i + (1 << (j - 1)), j - 1));
}
int lg(int x) { return 31 - __builtin_clz(x); }
int getmn(int l, int r) {
  int lz = lg(r - l + 1);
  return min(fn(l, lz), fn(r - (1 << lz) + 1, lz));
}
int comp_lcp(int i, int j) {
  if (i > j) swap(i, j);
  return getmn(i, j - 1);
}
int n;
string s[N];
int from[N];
int fromsa[N];
char str[N];
int sa[N], rsa[N];
int st[N];
int L[N], R[N];
int main() {
  memset(dn, -1, sizeof dn);
  int q;
  scanf("%d %d", &n, &q);
  int len = 0;
  for (int i = 0; i < n; i++) {
    scanf(" %s", str + len);
    s[i] = str + len;
    st[i] = len;
    for (int j = 0; j <= (int)s[i].size(); j++) {
      from[len + j] = i;
    }
    len += (int)s[i].size();
    str[len++] = '#';
  }
  str[len++] = '$';
  build_sa(str, len, sa);
  build_lcp(str, len, sa);
  for (int i = 0; i < len; i++) rsa[sa[i]] = i;
  for (int i = 0; i < len; i++) fromsa[i] = from[sa[i]];
  for (int i = 0; i < n; i++) {
    L[i] = rsa[st[i]];
    int sz = (int)s[i].size();
    int lo = 0, hi = rsa[st[i]] - 1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (comp_lcp(mid, rsa[st[i]]) >= sz) {
        L[i] = mid;
        hi = mid - 1;
      } else
        lo = mid + 1;
    }
    R[i] = rsa[st[i]];
    lo = R[i] + 1, hi = len - 1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (comp_lcp(rsa[st[i]], mid) >= sz) {
        R[i] = mid;
        lo = mid + 1;
      } else
        hi = mid - 1;
    }
  }
  wavelet<int> wt(fromsa, fromsa + len);
  while (q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    l--, r--, k--;
    int ans = 0;
    ans = wt.cnt(L[k] + 1, R[k] + 1, l - 1) - wt.cnt(L[k] + 1, R[k] + 1, r);
    printf("%d\n", ans);
  }
}