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 <class T, class F = function<T(const T &, const T &)>>
struct SparseTable {
  int n;
  vector<vector<T>> a;
  F func;
  SparseTable(const vector<T> &v, const F &f) : func(f) {
    n = (int)v.size();
    int max_log = 32 - __builtin_clz(n);
    a.resize(max_log);
    a[0] = v;
    for (int bit = 1; bit < max_log; bit++) {
      a[bit].resize(n - (1 << bit) + 1);
      for (int i = 0; i + (1 << bit) - 1 < n; i++) {
        a[bit][i] = func(a[bit - 1][i], a[bit - 1][i + (1 << (bit - 1))]);
      }
    }
  }
  T Get(int l, int r) const {
    assert(0 <= l && l <= r && r < n);
    int lg = 31 - __builtin_clz(r - l + 1);
    return func(a[lg][l], a[lg][r - (1 << lg) + 1]);
  }
};
struct Fenwick {
  int n;
  vector<int> tree;
  Fenwick(int n_) : n(n_), tree(n + 1) {}
  void Update(int pos, int val) {
    for (++pos; pos <= n; pos += pos & -pos) tree[pos] += val;
  }
  int Query(int l, int r) {
    if (l - 1 >= 0) return Query(0, r) - Query(0, l - 1);
    int ans = 0;
    for (int pos = r + 1; pos; pos -= pos & -pos) ans += tree[pos];
    return ans;
  }
};
vector<vector<vector<int>>> GetSA(const vector<string> &words, int input_size) {
  int log_sz = 33 - __builtin_clz(input_size);
  vector<vector<vector<int>>> order(log_sz, vector<vector<int>>(words.size()));
  for (int i = 0; i < (int)words.size(); ++i) {
    order[0][i].resize(words[i].size());
    for (int j = 0; j < (int)words[i].size(); ++j) {
      order[0][i][j] = words[i][j] - 'a';
    }
  }
  vector<tuple<int, int, int, int>> v(input_size);
  for (int lvl = 1; lvl < log_sz; ++lvl) {
    int idx = 0;
    for (int i = 0; i < (int)words.size(); ++i) {
      order[lvl][i].resize(words[i].size());
      for (int j = 0; j < (int)words[i].size(); ++j) {
        int fst = order[lvl - 1][i][j];
        int snd = (j + (1 << (lvl - 1))) < (int)words[i].size()
                      ? order[lvl - 1][i][j + (1 << (lvl - 1))]
                      : -1;
        v[idx++] = make_tuple(fst, snd, i, j);
      }
    }
    sort(v.begin(), v.end());
    int pos = 0, word, ch;
    tie(ignore, ignore, word, ch) = v[0];
    order[lvl][word][ch] = 0;
    for (int i = 1; i < (int)v.size(); ++i) {
      int lf, ls;
      tie(lf, ls, ignore, ignore) = v[i - 1];
      int f, s, w, j;
      tie(f, s, w, j) = v[i];
      if (lf != f || ls != s) ++pos;
      order[lvl][w][j] = pos;
    }
  }
  return order;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int n, q;
  cin >> n >> q;
  cin.get();
  vector<string> words(n);
  int input_size = 0;
  vector<vector<int>> idx_char(n);
  for (int i = 0; i < n; ++i) {
    getline(cin, words[i]);
    input_size += words[i].size();
    idx_char[i].resize(words[i].size());
  }
  auto sa = GetSA(words, input_size);
  vector<tuple<int, int, int>> order;
  order.reserve(input_size);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < (int)words[i].size(); ++j) {
      order.emplace_back(sa.back()[i][j], i, j);
    }
  }
  sort(order.begin(), order.end());
  for (int it = 0; it < input_size; ++it) {
    int idx, i, j;
    tie(idx, i, j) = order[it];
    idx_char[i][j] = it;
  }
  int log_sz = 32 - __builtin_clz(input_size);
  auto LCP_ = [&](int a, int b) {
    if (a >= input_size || b >= input_size) throw;
    int i0, j0;
    tie(ignore, i0, j0) = order[a];
    int i1, j1;
    tie(ignore, i1, j1) = order[b];
    int lcp = 0;
    for (int bit = log_sz - 1; bit >= 0; --bit) {
      if (j0 + (1 << bit) > (int)words[i0].size() ||
          j1 + (1 << bit) > (int)words[i1].size())
        continue;
      if (sa[bit][i0][j0] == sa[bit][i1][j1]) {
        lcp += 1 << bit;
        j0 += 1 << bit;
        j1 += 1 << bit;
      }
    }
    return lcp;
  };
  vector<int> cons_lcp(input_size - 1);
  for (int i = 0; i < input_size - 1; ++i) {
    cons_lcp[i] = LCP_(i, i + 1);
  }
  SparseTable<int> rmq(cons_lcp, [](int a, int b) { return min(a, b); });
  auto LCP = [&](int a, int b) {
    if (a == b) return (int)words[get<1>(order[a])].size() - get<2>(order[a]);
    if (a > b) swap(a, b);
    return rmq.Get(a, b - 1);
  };
  vector<vector<tuple<int, int, int>>> qrs(n);
  for (int i = 0; i < q; ++i) {
    int l, r, k;
    cin >> l >> r >> k;
    --l, --r, --k;
    if (l - 1 >= 0) qrs[l - 1].emplace_back(i, -1, k);
    qrs[r].emplace_back(i, +1, k);
  }
  auto BinSearchLeft = [&](int k) {
    int sz = words[k].size();
    k = idx_char[k][0];
    int lo = 0, hi = k, ans = -1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (LCP(mid, k) >= sz) {
        hi = mid - 1;
        ans = mid;
      } else {
        lo = mid + 1;
      }
    }
    return ans;
  };
  auto BinSearchRight = [&](int k) {
    int sz = words[k].size();
    k = idx_char[k][0];
    int lo = k, hi = input_size - 1, ans = -1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (LCP(mid, k) >= sz) {
        lo = mid + 1;
        ans = mid;
      } else {
        hi = mid - 1;
      }
    }
    return ans;
  };
  Fenwick fw(input_size);
  vector<int> ans(q);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < (int)words[i].size(); ++j) {
      fw.Update(idx_char[i][j], +1);
    }
    for (auto &qr : qrs[i]) {
      int idx, coef, k;
      tie(idx, coef, k) = qr;
      int l = BinSearchLeft(k), r = BinSearchRight(k);
      ans[idx] += coef * fw.Query(l, r);
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n';
  }
}