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>
const double EPS = 1e-4;
const long long int MOD = 1000000007ll;
const long long int HASHMOD[2] = {1000000009ll, 1100000009ll};
const double PI = 3.14159265359;
int INF = 2147483645;
long long int INFINF = 9223372036854775807;
int debug = 0;
template <class T>
T Max2(T a, T b) {
  return a < b ? b : a;
}
template <class T>
T Min2(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T Max3(T a, T b, T c) {
  return Max2(Max2(a, b), c);
}
template <class T>
T Min3(T a, T b, T c) {
  return Min2(Min2(a, b), c);
}
template <class T>
T Max4(T a, T b, T c, T d) {
  return Max2(Max2(a, b), Max2(c, d));
}
template <class T>
T Min4(T a, T b, T c, T d) {
  return Min2(Min2(a, b), Min2(c, d));
}
using namespace std;
long long int bit_count(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
long long int bit(long long int _mask, long long int _i) {
  return (_mask & (1 << _i)) == 0 ? 0 : 1;
}
long long int powermod(long long int _a, long long int _b, long long int _m) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int add(long long int a, long long int b) {
  long long int x = a + b;
  if (x > MOD) x -= MOD;
  return x;
}
long long int sub(long long int a, long long int b) {
  long long int x = a - b;
  if (x < 0) x += MOD;
  return x;
}
long long int mul(long long int a, long long int b) {
  long long int x = a * b;
  x %= MOD;
  return x;
}
static const int MAXN = 400010;
static const int MAXLOGN = 21;
string s;
int gap, sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN], logs[MAXN],
    lcptable[MAXN][MAXLOGN];
bool sufCmp(int i, int j) {
  if (pos[i] != pos[j]) return pos[i] < pos[j];
  i += gap;
  j += gap;
  return (i < (int)s.size() && j < (int)s.size()) ? pos[i] < pos[j] : i > j;
}
void buildSA() {
  for (int i = 0; i < (int)s.size(); i++) sa[i] = i, pos[i] = s[i];
  for (gap = 1;; gap *= 2) {
    sort(sa, sa + (int)s.size(), sufCmp);
    for (int i = 0; i < (int)s.size() - 1; i++)
      tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
    for (int i = 0; i < (int)s.size(); i++) pos[sa[i]] = tmp[i];
    if (tmp[(int)s.size() - 1] == (int)s.size() - 1) break;
  }
}
void buildLCP() {
  for (int i = 0, k = 0; i < (int)s.size(); ++i)
    if (pos[i] != (int)s.size() - 1) {
      for (int j = sa[pos[i] + 1]; s[i + k] == s[j + k];) ++k;
      lcp[pos[i]] = k;
      if (k) --k;
    }
}
void buildLogs() {
  int g = 2;
  while (g <= (int)s.size()) {
    logs[g] = 1;
    g = (g << 1);
  }
  for (int i = 1; i <= (int)s.size(); i++) logs[i] += logs[i - 1];
}
void buildLcpSparseTable() {
  for (int i = 0; i < (int)s.size(); i++) lcptable[i][0] = lcp[i];
  for (int j = 1; (1 << j) <= (int)s.size(); j++)
    for (int i = 0; i + (1 << j) - 1 < (int)s.size(); i++)
      lcptable[i][j] =
          Min2(lcptable[i][j - 1], lcptable[i + (1 << (j - 1))][j - 1]);
}
int lcpQuery(int l, int r) {
  if (l > r) swap(l, r);
  if (l == r) return INF;
  if (l + 1 == r) return lcp[l];
  r--;
  int k = logs[r - l + 1];
  return Min2(lcptable[l][k], lcptable[r - (1 << k) + 1][k]);
}
void update(int s, int e, int x, int idx, int *segtree) {
  if (s == e)
    segtree[idx] = 1;
  else {
    int mid = (s + e) >> 1;
    if (x <= mid)
      update(s, mid, x, 2 * idx + 1, segtree);
    else
      update(mid + 1, e, x, 2 * idx + 2, segtree);
    segtree[idx] = segtree[2 * idx + 1] + segtree[2 * idx + 2];
  }
}
int query(int s, int e, int x, int y, int idx, int *segtree) {
  if (s == x && e == y) return segtree[idx];
  int mid = (s + e) >> 1;
  if (y <= mid)
    return query(s, mid, x, y, 2 * idx + 1, segtree);
  else if (x > mid)
    return query(mid + 1, e, x, y, 2 * idx + 2, segtree);
  else
    return query(s, mid, x, mid, 2 * idx + 1, segtree) +
           query(mid + 1, e, mid + 1, y, 2 * idx + 2, segtree);
}
int n, q, N;
int stringsz[200010];
char tempstring[200010];
pair<int, int> queryRange[200010];
int beginning[200010], ending[200010];
int ans[500010];
vector<pair<int, pair<int, int> > > queries[200010];
int segtree[1600010];
int main() {
  srand(time(NULL));
  scanf("%d", &n);
  scanf("%d", &q);
  for (int i = 0; i < n; i++) {
    beginning[i] = s.size();
    scanf("%s", tempstring);
    ;
    stringsz[i] = strlen(tempstring);
    s += tempstring;
    ending[i] = s.size() - 1;
    s += '$';
  }
  N = s.size();
  buildSA();
  buildLCP();
  buildLogs();
  buildLcpSparseTable();
  for (int i = 0; i < n; i++) {
    int idx = pos[beginning[i]];
    int high, low, mid, l, r;
    low = 0, high = idx;
    while (low <= high) {
      mid = (low + high) >> 1;
      if (lcpQuery(mid, idx) >= stringsz[i]) {
        l = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    low = idx, high = N - 1;
    while (low <= high) {
      mid = (low + high) >> 1;
      if (lcpQuery(mid, idx) >= stringsz[i]) {
        r = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    queryRange[i] = {l, r};
    assert(l >= 0 && l <= idx && r >= idx && r <= N - 1);
  }
  for (int i = 0; i < q; i++) {
    int l, r, k;
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", &k);
    l--, k--, r--;
    if (l != 0) queries[l - 1].push_back({-1, {i, k}});
    queries[r].push_back({1, {i, k}});
  }
  for (int i = 0; i < n; i++) {
    for (int j = beginning[i]; j <= ending[i]; j++) {
      update(0, N - 1, pos[j], 0, segtree);
    }
    for (pair<int, pair<int, int> > it : queries[i]) {
      int k = it.second.second;
      ans[it.second.first] +=
          it.first * query(0, N - 1, queryRange[k].first, queryRange[k].second,
                           0, segtree);
    }
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}