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]);
}
struct Node {
  int cnt;
  Node *l, *r;
  Node() {
    cnt = 0;
    l = r = NULL;
  }
};
void build(Node* curr, int s, int e) {
  if (s == e) {
    return;
  } else {
    int mid = (s + e) >> 1;
    curr->l = new Node();
    curr->r = new Node();
    build(curr->l, s, mid);
    build(curr->r, mid + 1, e);
  }
}
void makeTree(Node* prev, Node* curr, int s, int e, int x) {
  if (s == e) {
    curr->cnt = prev->cnt + 1;
    return;
  }
  int mid = (s + e) >> 1;
  if (x <= mid) {
    curr->l = new Node();
    curr->cnt = prev->cnt + 1;
    curr->r = prev->r;
    makeTree(prev->l, curr->l, s, mid, x);
  } else {
    curr->r = new Node();
    curr->cnt = prev->cnt + 1;
    curr->l = prev->l;
    makeTree(prev->r, curr->r, mid + 1, e, x);
  }
}
int query(Node* prev, Node* curr, int s, int e, int x, int y) {
  if (s == x && e == y) return curr->cnt - prev->cnt;
  int mid = (s + e) >> 1;
  if (y <= mid)
    return query(prev->l, curr->l, s, mid, x, y);
  else if (x > mid)
    return query(prev->r, curr->r, mid + 1, e, x, y);
  return query(prev->l, curr->l, s, mid, x, mid) +
         query(prev->r, curr->r, mid + 1, e, mid + 1, y);
}
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];
Node *root[400010], *baseroot;
int whichString[400010];
int main() {
  srand(time(NULL));
  for (int i = 0; i < 400010; i++) whichString[i] = -1;
  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 += '$';
    for (int j = beginning[i]; j <= ending[i]; j++) whichString[j] = i;
  }
  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);
  }
  baseroot = new Node();
  build(baseroot, 0, n - 1);
  for (int i = 0; i < N; i++) {
    if (whichString[sa[i]] != -1) {
      root[i] = new Node();
      makeTree(i == 0 ? baseroot : root[i - 1], root[i], 0, n - 1,
               whichString[sa[i]]);
    } else
      root[i] = (i == 0) ? baseroot : root[i - 1];
  }
  while (q--) {
    int l, r, k;
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", &k);
    l--;
    r--;
    k--;
    printf("%d\n",
           query((queryRange[k].first == 0) ? baseroot
                                            : root[queryRange[k].first - 1],
                 root[queryRange[k].second], 0, n - 1, l, r));
  }
  return 0;
}