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 MAXN = 400100;
const int LEAVES = 1 << 19;
int s[MAXN];
char tmpp[MAXN];
int delim = 266;
int sa[MAXN], tmp[MAXN], cnt[MAXN], rnk[MAXN], lcp[MAXN], pos[MAXN], ranks;
int n;
int l, r, k;
int q;
int st[20][MAXN];
int Log[MAXN];
int N;
int L[MAXN];
int R[MAXN];
int start[MAXN];
int len[MAXN];
vector<int> t[2 * LEAVES];
void buildSparse() {
  for (int i = 0; i < n; ++i) st[0][i] = lcp[i];
  for (int i = 1; i < 20; ++i) {
    for (int j = 0; j + (1 << i) <= n; ++j) {
      st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
  }
}
void build() {
  for (int i = 0; i < n; ++i) {
    ++cnt[(int)s[i]];
  }
  for (int i = 1; i < MAXN; ++i) {
    cnt[i] += cnt[i - 1];
  }
  for (int i = 0; i < n; ++i) {
    sa[--cnt[(int)s[i]]] = i;
  }
  memset(cnt, 0, sizeof(int) * MAXN);
  rnk[sa[0]] = 0;
  ranks = 1;
  for (int i = 1; i < n; ++i) {
    if (s[sa[i]] != s[sa[i - 1]])
      rnk[sa[i]] = ranks++;
    else
      rnk[sa[i]] = rnk[sa[i - 1]];
  }
  for (int step = 1; step < n; step <<= 1) {
    for (int i = 0; i < n; ++i) {
      tmp[i] = sa[i] - step;
      if (tmp[i] < 0) tmp[i] += n;
    }
    for (int i = 0; i < n; ++i) {
      ++cnt[rnk[i]];
    }
    for (int i = 1; i < ranks; ++i) {
      cnt[i] += cnt[i - 1];
    }
    for (int i = n - 1; i > -1; --i) {
      sa[--cnt[rnk[tmp[i]]]] = tmp[i];
    }
    memset(cnt, 0, sizeof(int) * ranks);
    tmp[sa[0]] = 0;
    ranks = 1;
    for (int i = 1; i < n; ++i) {
      if (rnk[sa[i]] != rnk[sa[i - 1]] ||
          rnk[(sa[i] + step) % n] != rnk[(sa[i - 1] + step) % n])
        tmp[sa[i]] = ranks++;
      else
        tmp[sa[i]] = tmp[sa[i - 1]];
    }
    memcpy(rnk, tmp, sizeof(int) * n);
  }
}
void kasai() {
  for (int i = 0; i < n; ++i) pos[sa[i]] = i;
  for (int i = 0, k = 0; i < n; ++i) {
    if (pos[i] == n - 1) {
      k = 0;
      continue;
    }
    int j = sa[pos[i] + 1];
    while (s[i + k] == s[j + k]) ++k;
    lcp[pos[i]] = k;
    if (k > 0) --k;
  }
}
inline int getMin(int l, int r) {
  if (l > r) return 1e9;
  int L = Log[r - l + 1];
  return min(st[L][l], st[L][r - (1 << L) + 1]);
}
int get(int v, int tl, int tr, int l, int r, int val) {
  if (l > r) return 0;
  if (tl == l && tr == r) {
    return upper_bound(t[v].begin(), t[v].end(), val) - t[v].begin();
  }
  int tm = (tl + tr) >> 1;
  return get(v << 1, tl, tm, l, min(r, tm), val) +
         get(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, val);
}
inline int getRange(int l, int r, int val) {
  return get(1, 0, LEAVES - 1, l, r, val);
}
int solve(int l, int r, int k) {
  int lt = -1;
  int rt = pos[start[k]];
  while (rt - lt > 1) {
    int mid = (lt + rt) >> 1;
    if (getMin(mid, pos[start[k]] - 1) >= len[k])
      rt = mid;
    else
      lt = mid;
  }
  int lUp = rt;
  lt = pos[start[k]] - 1;
  rt = n;
  while (rt - lt > 1) {
    int mid = (lt + rt) >> 1;
    if (getMin(pos[start[k]], mid - 1) >= len[k])
      lt = mid;
    else
      rt = mid;
  }
  int rUp = lt;
  return max(0, getRange(lUp, rUp, R[r]) - getRange(lUp, rUp, L[l] - 1));
}
void merge(vector<int> &t, vector<int> &t1, vector<int> &t2) {
  int it1 = 0, it2 = 0;
  while (it1 < (int)t1.size() && it2 < (int)t2.size()) {
    if (t1[it1] < t2[it2]) {
      t.push_back(t1[it1++]);
    } else {
      t.push_back(t2[it2++]);
    }
  }
  while (it1 < (int)t1.size()) {
    t.push_back(t1[it1++]);
  }
  while (it2 < (int)t2.size()) {
    t.push_back(t2[it2++]);
  }
}
int main() {
  Log[1] = 0;
  for (int i = 2; i < MAXN; ++i) Log[i] = Log[i >> 1] + 1;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; ++i) {
    scanf("%s", tmpp);
    L[i] = N;
    for (int j = 0; tmpp[j]; ++j) {
      ++len[i];
      s[N++] = tmpp[j];
    }
    R[i] = N;
    start[i] = L[i];
    s[N++] = delim++;
  }
  s[N - 1] = 0;
  n = N;
  build();
  kasai();
  buildSparse();
  for (int i = 0; i < N; ++i) t[LEAVES + i].push_back(sa[i]);
  for (int i = LEAVES - 1; i > 0; --i) merge(t[i], t[i << 1], t[i << 1 | 1]);
  while (q-- > 0) {
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", solve(l - 1, r - 1, k - 1));
  }
  return 0;
}