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 T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& a) {
  in >> a.first >> a.second;
  return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> a) {
  out << a.first << " " << a.second;
  return out;
}
template <typename T, typename T1>
T maxs(T& a, T1 b) {
  if (b > a) a = b;
  return a;
}
template <typename T, typename T1>
T mins(T& a, T1 b) {
  if (b < a) a = b;
  return a;
}
template <typename T>
struct suffix_array {
  T s;
  vector<long long> p, c;
  vector<long long> lcp, len;
  long long n;
  suffix_array(T str) {
    s = str;
    n = s.size();
    p.resize(n);
    c.resize(n);
    lcp.resize(n);
    len.resize(n);
  }
  void count_sort(vector<long long>& p, vector<long long>& c) {
    long long n = p.size();
    vector<long long> cnt(n);
    for (auto first : c) cnt[first]++;
    vector<long long> p_new(n), pos(n);
    pos[0] = 0;
    for (long long i = 1; i < n; i++) pos[i] = pos[i - 1] + cnt[i - 1];
    for (auto first : p) {
      long long i = c[first];
      p_new[pos[i]] = first;
      pos[i]++;
    }
    p = p_new;
  }
  void build() {
    vector<pair<long long, long long>> a(n);
    for (long long i = 0; i < n; i++) a[i] = {s[i], i};
    sort(a.begin(), a.end());
    for (long long i = 0; i < n; i++) p[i] = a[i].second;
    c[p[0]] = 0;
    for (long long i = 1; i < n; i++)
      c[p[i]] = (a[i].first == a[i - 1].first) ? c[p[i - 1]] : c[p[i - 1]] + 1;
    long long k = 0;
    while ((1 << k) < n) {
      for (long long i = 0; i < n; i++) p[i] = (p[i] - (1 << k) + n) % n;
      count_sort(p, c);
      vector<long long> c_new(n);
      c_new[p[0]] = 0;
      for (long long i = 1; i < n; i++) {
        pair<long long, long long> prev = {c[p[i - 1]],
                                           c[(p[i - 1] + (1 << k)) % n]};
        pair<long long, long long> now = {c[p[i]], c[(p[i] + (1 << k)) % n]};
        if (now == prev) {
          c_new[p[i]] = c_new[p[i - 1]];
        } else {
          c_new[p[i]] = c_new[p[i - 1]] + 1;
        }
      }
      c = c_new;
      k++;
    }
    for (long long i = 0; i < n; i++) {
      len[i] = n - p[i];
    }
    k = 0;
    for (long long i = 0; i < n - 1; i++) {
      long long pi = c[i];
      long long j = p[pi - 1];
      while (s[i + k] == s[j + k]) k++;
      lcp[pi] = k;
      k = max(0LL, k - 1);
    }
  }
};
vector<long long> label, s;
vector<string> a;
template <typename T>
struct Fenwick {
  vector<T> tree;
  Fenwick(long long n) { tree.resize(n); }
  T query(long long i) {
    long long sum = 0;
    while (i) {
      sum += tree[i];
      i -= i & (-i);
    }
    return sum;
  }
  void update(long long i, long long n, T val) {
    while (i <= n) {
      tree[i] += val;
      i += i & (-i);
    }
  }
};
long long solve() {
  long long n, q;
  cin >> n >> q;
  a.resize(n + 1);
  set<long long> imp;
  map<long long, long long> mp;
  for (long long i = 1; i < n + 1; i++) {
    cin >> a[i];
    imp.insert((long long)label.size());
    mp[(long long)label.size()] = a[i].length();
    for (auto j : a[i]) s.push_back(j), label.push_back(i);
    label.push_back(0);
    s.push_back(-i);
  }
  suffix_array<vector<long long>> sa(s);
  sa.build();
  long long m = s.size();
  vector<long long> pl(m), impl;
  for (long long i = 0; i < m; i++) pl[i] = label[sa.p[i]];
  for (long long i = 0; i < m; i++) {
    if (imp.count(sa.p[i])) {
      impl.push_back(i);
    }
  }
  vector<pair<long long, long long>> vec(n + 1);
  for (auto i : impl) {
    long long l = i, r = m - 1;
    long long len = mp[sa.p[i]];
    vec[pl[i]].first = i, vec[pl[i]].second = i;
    while (l <= r) {
      long long mid = (l + r) / 2;
      bool f = 1;
      for (long long k = 0; k < len; k++) {
        long long x1 = s[sa.p[i] + k];
        long long x2 = s[sa.p[mid] + k];
        if (x1 != x2) {
          f = 0;
          break;
        }
      }
      if (f) {
        l = mid + 1;
        vec[pl[i]].second = mid;
      } else {
        r = mid - 1;
      }
    }
    l = 1, r = i;
    while (l <= r) {
      long long mid = (l + r) / 2;
      bool f = 1;
      for (long long k = 0; k < len; k++) {
        long long x1 = s[sa.p[i] + k];
        long long x2 = s[sa.p[mid] + k];
        if (x1 != x2) {
          f = 0;
          break;
        }
      }
      if (f) {
        r = mid - 1;
        vec[pl[i]].first = mid;
      } else {
        l = mid + 1;
      }
    }
  }
  vector<long long> ans(q + 1);
  vector<pair<long long, pair<long long, long long>>> query;
  for (long long i = 1; i < q + 1; i++) {
    long long l, r, k;
    cin >> l >> r >> k;
    query.push_back({l, {i, k}});
    query.push_back({r + 1, {-i, k}});
  }
  sort(query.begin(), query.end());
  Fenwick<long long> fn(m + 1);
  map<long long, vector<long long>> st;
  for (long long i = 1; i < m; i++) {
    if (pl[i] > 0) {
      fn.update(i, m, 1);
      st[pl[i]].push_back(i);
    }
  }
  long long j = 0;
  for (long long i = 1; i < n + 1; i++) {
    while (j < (long long)query.size() && query[j].first == i) {
      long long idx = query[j].second.first;
      long long l = vec[query[j].second.second].first;
      long long r = vec[query[j].second.second].second;
      long long val = fn.query(r) - fn.query(l - 1);
      if (idx > 0)
        ans[idx] += val;
      else
        ans[-idx] -= val;
      j++;
    }
    for (auto j : st[i]) {
      fn.update(j, m, -1);
    }
  }
  for (long long i = 1; i < q + 1; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}