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 long long MOD = 1e9 + 7;
const int INF = 1e9;
const long long INF64 = 1e18;
const double EPS = 1e-9;
const double PI = acos(-1);
const long long MD = 1551513443;
const long long T = 25923;
const int N = 400100;
const int M = 3010;
int lg[N];
struct SparseTable {
  int *t[20], n;
  inline void build(int n, int* p) {
    lg[1] = 0;
    for (int i = 2; i < N; i++) lg[i] = lg[i / 2] + 1;
    this->n = n;
    for (int i = 0; i < int(20); i++) t[i] = new int[n];
    for (int i = 0; i < int(n); i++) t[0][i] = p[i];
    for (int h = 1; h < 20; h++)
      for (int i = 0; i < n - (1 << h) + 1; i++)
        t[h][i] = min(t[h - 1][i], t[h - 1][i + (1 << (h - 1))]);
  }
  inline int get_min(int l, int r) {
    int q = lg[r - l + 1];
    return min(t[q][l], t[q][r - (1 << q) + 1]);
  }
} sp;
int n, m, qq, ind[N];
string name[N], s;
int c[20][N], cnt[N], p[N], pn[N], p1[N], lcp[N];
inline void buildSuffixArray() {
  int alphabet = 500;
  for (int i = 0; i < int(m); i++) cnt[s[i]]++;
  for (int i = 1; i < alphabet; i++) cnt[i] += cnt[i - 1];
  for (int i = 0; i < int(m); i++) p[--cnt[s[i]]] = i;
  int color = 0;
  c[0][p[0]] = color;
  for (int i = 1; i < m; i++) {
    if (s[p[i]] != s[p[i - 1]]) color++;
    c[0][p[i]] = color;
  }
  for (int h = 0; (1 << h) < m; h++) {
    for (int i = 0; i < int(m); i++) {
      pn[i] = p[i] - (1 << h);
      if (pn[i] < 0) pn[i] += m;
    }
    fill(cnt, cnt + m, 0);
    for (int i = 0; i < int(m); i++) cnt[c[h][pn[i]]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = m - 1; i >= 0; i--) p[--cnt[c[h][pn[i]]]] = pn[i];
    color = 0;
    c[h + 1][p[0]] = color;
    for (int i = 1; i < m; i++) {
      int mid1 = (p[i] + (1 << h)) % m, mid2 = (p[i - 1] + (1 << h)) % m;
      if (c[h][p[i]] != c[h][p[i - 1]] || c[h][mid1] != c[h][mid2]) color++;
      c[h + 1][p[i]] = color;
    }
  }
}
inline int get_lcp(int a, int b) {
  int ans = 0;
  for (int i = int(floor(log2(m))); i >= 0; i--)
    if (c[i][a] == c[i][b]) {
      ans += (1 << i);
      a += (1 << i);
      b += (1 << i);
    }
  return ans;
}
vector<int> t[N * 4];
inline void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v].push_back(p[tl]);
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v].resize(int((t[v * 2]).size()) + int((t[v * 2 + 1]).size()));
    merge((t[v * 2]).begin(), (t[v * 2]).end(), (t[v * 2 + 1]).begin(),
          (t[v * 2 + 1]).end(), t[v].begin());
  }
}
inline int get(int v, int tl, int tr, int l, int r, int first) {
  if (l > r) return 0;
  if (tl == l && tr == r) {
    return int(upper_bound((t[v]).begin(), (t[v]).end(), first) - t[v].begin());
  } else {
    int tm = (tl + tr) / 2;
    return get(v * 2, tl, tm, l, min(r, tm), first) +
           get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, first);
  }
}
int main() {
  cin >> n >> qq;
  for (int i = 0; i < int(n); i++) {
    cin >> name[i];
    ind[i] = int((s).size());
    s += name[i];
    s += "$";
  }
  s += char('$' - 1);
  m = int((s).size());
  buildSuffixArray();
  build(1, 0, m - 1);
  for (int i = 0; i < int(m); i++) p1[p[i]] = i;
  for (int i = 0; i < int(m - 1); i++) lcp[i] = get_lcp(p[i], p[i + 1]);
  sp.build(m, lcp);
  for (int u = 0; u < int(qq); u++) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    l--;
    r--;
    k--;
    int first = p1[ind[k]], second = p1[ind[k]];
    {
      int l = -1, r = first;
      while (r - l > 1) {
        int mm = (l + r) / 2;
        if (sp.get_min(mm, first - 1) >= int((name[k]).size()))
          r = mm;
        else
          l = mm;
      }
      first = r;
    }
    {
      int l = second, r = m;
      while (r - l > 1) {
        int mm = (l + r) / 2;
        if (sp.get_min(second, mm - 1) >= int((name[k]).size()))
          l = mm;
        else
          r = mm;
      }
      second = l;
    }
    printf("%d\n", get(1, 0, m - 1, first, second,
                       ind[r] + int((name[r]).size()) - int((name[k]).size())) -
                       get(1, 0, m - 1, first, second, ind[l] - 1));
  }
  return 0;
}