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;
const int inf = 1e9;
const long long INF = 1e18;
const double eps = 1e-10;
mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T>
inline void upmin(T &x, T y) {
  x = x > y ? y : x;
}
template <class T>
inline void upmax(T &x, T y) {
  x = x < y ? y : x;
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class A, class B, class C>
string to_string(tuple<A, B, C> p);
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <class A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A, class B, class C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <class T, class... U>
void debug(const T &h, const U &...t) {
  cerr << to_string(h) << ' ';
  debug(t...);
}
const int maxn = 2e5 + 233;
int n, q;
char s[maxn];
template <class T>
struct Merge_Segment_Tree {
  int ls[maxn << 5], rs[maxn << 5], root[maxn << 5];
  int sz;
  T sum[maxn << 5];
  void update(int &o, int l, int r, int p, int v) {
    if (!o) o = ++sz;
    sum[o] += v;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid)
      update(ls[o], l, mid, p, v);
    else
      update(rs[o], mid + 1, r, p, v);
  }
  int merge(int u, int v) {
    if (!u || !v) return u + v;
    int t = ++sz;
    ls[t] = merge(ls[u], ls[v]);
    rs[t] = merge(rs[u], rs[v]);
    sum[t] = sum[u] + sum[v];
    return t;
  }
  T query(int o, int tl, int tr, int l, int r) {
    if (!o) return 0;
    if (l <= tl && tr <= r) return sum[o];
    int mid = tl + tr >> 1;
    T res = 0;
    if (l <= mid) res += query(ls[o], tl, mid, l, r);
    if (r > mid) res += query(rs[o], mid + 1, tr, l, r);
    return res;
  }
};
Merge_Segment_Tree<long long> tr;
struct SAM {
  int len[maxn * 2];
  int f[maxn * 2];
  int cnt[maxn * 2];
  int ch[maxn * 2][26];
  int sz;
  int last;
  long long epos[maxn * 2];
  long long a[maxn];
  int deg[maxn * 2];
  vector<int> G[maxn * 2];
  void init() {
    last = sz = 1;
    f[1] = len[1] = 0;
    memset(ch[1], 0, sizeof(ch[1]));
  }
  void add(int c) {
    if (ch[last][c] && len[ch[last][c]] == len[last] + 1) {
      last = ch[last][c];
      epos[last]++;
      return;
    }
    int x = ++sz;
    len[x] = len[last] + 1;
    epos[x] = 1;
    int p;
    for (p = last; p && !ch[p][c]; p = f[p]) ch[p][c] = x;
    if (!p)
      f[x] = 1, cnt[1]++;
    else {
      int q = ch[p][c];
      int ff = 0;
      if (len[x] == len[p] + 1) ff = 1;
      if (len[p] + 1 == len[q])
        f[x] = q, cnt[q]++;
      else {
        int nq = ++sz;
        len[nq] = len[p] + 1;
        f[nq] = f[q];
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        for (; p && ch[p][c] == q; p = f[p]) ch[p][c] = nq;
        f[q] = f[x] = nq;
        cnt[nq] += 2;
        if (ff)
          last = nq;
        else
          last = x;
        return;
      }
    }
    last = x;
  }
  void getpos() {
    queue<int> q;
    for (int i = 1; i <= sz; i++)
      if (!cnt[i]) q.push(i);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      epos[f[x]] += epos[x];
      if (--cnt[f[x]] == 0) q.push(f[x]);
    }
  }
  void getsubnum() {
    long long ans = 0;
    for (int i = 2; i <= sz; i++) ans += len[i] - len[f[i]];
    printf("%lld\n", ans);
  }
  void getsubmax() {
    getpos();
    int n = strlen(s);
    for (int i = 1; i <= sz; i++) a[len[i]] = max(a[len[i]], epos[i]);
    for (int i = n - 1; i >= 1; i--) a[i] = max(a[i], a[i + 1]);
    for (int i = 1; i <= n; i++) printf("%lld\n", a[i]);
  }
  void getdeg() {
    for (int i = 1; i <= sz; i++) {
      for (int j = 0; j < 26; j++) {
        int v = ch[i][j];
        if (v) deg[v]++;
      }
    }
  }
  void build() {
    for (int i = 2; i <= sz; i++) {
      G[f[i]].emplace_back(i);
    }
    dfs(1);
  }
  void dfs(int u) {
    for (auto v : G[u])
      dfs(v), epos[u] += epos[v], tr.root[u] = tr.merge(tr.root[u], tr.root[v]);
  }
} sam;
int pos[maxn];
int main() {
  scanf("%d %d", &n, &q);
  sam.init();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    for (int j = 1, len = strlen(s + 1); j <= len; j++) {
      sam.add(s[j] - 'a');
      tr.update(tr.root[sam.last], 1, n, i, 1);
    }
    pos[i] = sam.last;
    sam.last = 1;
  }
  sam.build();
  while (q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    k = pos[k];
    printf("%lld\n", tr.query(tr.root[k], 1, n, l, r));
  }
  return 0;
}