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 Mod = 1000696969, N = 200005;
vector<int> H[N];
int64_t Base[N];
int n, q, realPos[N];
pair<int, int> bounds[N];
string s[N];
struct Query {
  int l, r, num, sign, index;
  Query() { l = r = num = sign = index = 0; }
  Query(int _l, int _r, int _num, int _sign, int _index)
      : l(_l), r(_r), num(_num), sign(_sign), index(_index) {}
  bool operator<(const Query &u) const { return num > u.num; }
};
namespace Kquery {
struct Fenwick_Tree {
  int bit[N];
  Fenwick_Tree() { memset(bit, 0, sizeof bit); }
  void update(int index) {
    while (index < N) bit[index]++, index += index & (-index);
  }
  int get(int index) {
    int res = 0;
    while (index != 0) res += bit[index], index -= index & (-index);
    return res;
  }
};
vector<int> solve(vector<Query> &Q, vector<pair<int, int> > &A) {
  Fenwick_Tree T;
  vector<int> Ans(Q.size() >> 1);
  int l = 0;
  for (int i = 0; i < (int)Q.size(); ++i) {
    while (Q[i].num <= A[l].first) T.update(A[l++].second);
    Ans[Q[i].index] += Q[i].sign * (T.get(Q[i].r) - T.get(Q[i].l - 1));
  }
  return Ans;
}
}  // namespace Kquery
int getHash(int index, int l, int r) {
  assert(l <= r);
  int res = (H[index][r] - H[index][l - 1] * Base[r - l + 1]) % Mod;
  return (res >= 0) ? res : (res + Mod);
}
struct Suffix {
  int index, pos, length;
  Suffix() { index = pos = length = 0; }
  Suffix(int _index, int _pos, int _length)
      : index(_index), pos(_pos), length(_length) {}
  int CommonLength(const Suffix &a) const {
    int l = 0, r = min(length, a.length);
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      int x = getHash(index, pos, pos + mid - 1);
      int y = getHash(a.index, a.pos, a.pos + mid - 1);
      if (x == y)
        l = mid;
      else
        r = mid - 1;
    }
    return l;
  }
  bool operator<(const Suffix &a) const {
    int l = CommonLength(a);
    if (l == min(length, a.length)) return length < a.length;
    return s[index][pos + l] < s[a.index][a.pos + l];
  }
} SufArr[N];
int main() {
  scanf("%d%d", &n, &q);
  Base[0] = 1;
  for (int i = 1; i < N; ++i) Base[i] = Base[i - 1] * 307 % Mod;
  int total = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
    s[i] = "!" + s[i];
    H[i].resize(s[i].size());
    for (int j = 1; j < (int)s[i].size(); ++j) {
      H[i][j] = (H[i][j - 1] * 307ll + s[i][j] - 'a' + 1) % Mod;
      SufArr[++total] = Suffix(i, j, s[i].size() - j);
    }
  }
  sort(SufArr + 1, SufArr + total + 1);
  for (int i = 1; i <= total; ++i) {
    if (SufArr[i].pos != 1) continue;
    realPos[SufArr[i].index] = i;
    int l = i, r = total;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (SufArr[i].CommonLength(SufArr[mid]) >= SufArr[i].length)
        l = mid;
      else
        r = mid - 1;
    }
    bounds[i].second = l;
    l = 1, r = i;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (SufArr[i].CommonLength(SufArr[mid]) >= SufArr[i].length)
        r = mid;
      else
        l = mid + 1;
    }
    bounds[i].first = l;
  }
  vector<Query> Q;
  Q.reserve(q << 1);
  for (int i = 0; i < q; ++i) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    k = realPos[k];
    Q.emplace_back(Query(bounds[k].first, bounds[k].second, l, 1, i));
    Q.emplace_back(Query(bounds[k].first, bounds[k].second, r + 1, -1, i));
  }
  sort(Q.begin(), Q.end());
  vector<pair<int, int> > A;
  A.reserve(total + 1);
  for (int i = 1; i <= total; ++i)
    A.emplace_back(make_pair(SufArr[i].index, i));
  A.emplace_back(make_pair(-1, N));
  sort(A.begin(), A.end(), greater<pair<int, int> >());
  vector<int> res = Kquery::solve(Q, A);
  for (int i = 0; i < q; ++i) printf("%d\n", res[i]);
}