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;
struct arr_entry {
  int index;
  int value;
  arr_entry(int index, int value) : index(index), value(value) {}
  bool operator<(arr_entry e2) const {
    if (value == e2.value) return index < e2.index;
    return value < e2.value;
  }
};
struct lowers_prefix_query {
  int n;
  int* arr;
  int q;
  int* fenwick;
  set<arr_entry> entries;
  lowers_prefix_query(int* arr, int n) : n(n), q(-1), entries() {
    this->arr = new int[n];
    for (int i = 0; i < n; i++) this->arr[i] = arr[i];
    fenwick = new int[n];
  }
  void reset() {
    entries.clear();
    for (int i = 0; i < n; i++) {
      fenwick[i] = 0;
      entries.insert(arr_entry(i, arr[i]));
    }
    q = -1;
  }
  void prepareQuery(int q) {
    if (q < this->q) {
      cout << "ASSERT FAILED" << endl;
      reset();
    }
    this->q = q;
    while (!entries.empty() && entries.begin()->value <= q) {
      arr_entry e = *entries.begin();
      entries.erase(e);
      for (int i = e.index; i < n; i |= (i + 1)) fenwick[i]++;
    }
  }
  int query(int len) {
    int count = 0;
    while (len > 0) {
      count += fenwick[len - 1];
      len &= (len - 1);
    }
    return count;
  }
  int query(int begin, int end) { return query(end) - query(begin); }
};
int* suffixArray(int* str, int n) {
  int* suff = new int[n + 1];
  for (int i = 0; i <= n; i++) suff[i] = i;
  struct comparer {
    int n;
    int d;
    int* ranks;
    bool operator()(int i, int j) {
      if (ranks[i] != ranks[j]) return ranks[i] < ranks[j];
      int ri = (i + d < n ? ranks[i + d] : -1);
      int rj = (j + d < n ? ranks[j + d] : -1);
      return ri < rj;
    }
  };
  int* tRanks = new int[n];
  comparer comp;
  comp.ranks = new int[n];
  comp.n = n;
  for (int i = 0; i < n; i++) {
    comp.ranks[i] = str[i];
  }
  for (comp.d = 0; comp.d < n; comp.d = comp.d ? (2 * comp.d) : 1) {
    sort(suff, suff + n, comp);
    int r = 0;
    for (int i = 0; i < n; i++) {
      if (i != 0 && comp(suff[i - 1], suff[i])) {
        r++;
      }
      tRanks[suff[i]] = r;
    }
    for (int i = 0; i < n; i++) {
      comp.ranks[i] = tRanks[i];
    }
  }
  delete[] comp.ranks;
  delete[] tRanks;
  return suff;
}
int* suffixInverseArray(int* suff, int n) {
  int* suffInv = new int[n + 1];
  for (int i = 0; i <= n; i++) suffInv[suff[i]] = i;
  return suffInv;
}
int* lcpArray(int* str, int* suff, int* suffInv, int n) {
  int* lcp = new int[n];
  int h = 0;
  for (int i = 0; i < n; i++) {
    int j = suff[suffInv[i] + 1];
    while (i + h < n && j + h < n && str[i + h] == str[j + h]) ++h;
    lcp[i] = h;
    if (h > 0) --h;
  }
  return lcp;
}
struct RMQ {
  int n;
  int** data;
  int* log;
  RMQ() {}
  RMQ(int* arr, int n) : n(n) {
    log = new int[n + 1];
    log[0] = 0;
    for (int i = 1; i <= n; i++) log[i] = log[i / 2] + 1;
    int levels = log[n] + 1;
    data = new int*[levels];
    data[0] = new int[n];
    for (int i = 0; i < n; i++) data[0][i] = arr[i];
    for (int t = 1; t < levels; t++) {
      data[t] = new int[n];
      int gap = 1 << (t - 1);
      for (int i = 0, j = gap; i < n; i++, j = min(j + 1, n - 1)) {
        data[t][i] = min(data[t - 1][i], data[t - 1][j]);
      }
    }
  }
  int query(int i, int j) {
    int t = log[j - i];
    int gap = 1 << (t - 1);
    return min(data[t - 1][i], data[t - 1][j - gap]);
  }
};
struct LCP {
  int n;
  int* suffInv;
  RMQ rmq;
  LCP(int* suffInv, int* lcpSuffArr, int n) : n(n) {
    this->suffInv = new int[n];
    for (int i = 0; i < n; i++) this->suffInv[i] = suffInv[i];
    this->rmq = RMQ(lcpSuffArr, n);
  }
  int query(int i, int j) {
    if (i == j) return n - i;
    int si = suffInv[i];
    int sj = suffInv[j];
    if (si < sj)
      return rmq.query(si, sj);
    else
      return rmq.query(sj, si);
  }
};
int lowerBound(LCP& lcp, int* suff, int i, int len) {
  int minIndex = 0, maxIndex = lcp.suffInv[i];
  while (maxIndex - minIndex > 0) {
    int d = (minIndex + maxIndex) / 2;
    int lcpValue = lcp.query(i, suff[d]);
    if (lcpValue >= len) {
      maxIndex = d;
    } else {
      minIndex = d + 1;
    }
  }
  return maxIndex;
}
int upperBound(LCP& lcp, int* suff, int i, int len) {
  int minIndex = lcp.suffInv[i], maxIndex = lcp.n;
  while (maxIndex - minIndex > 0) {
    int d = (minIndex + maxIndex) / 2;
    int lcpValue = lcp.query(i, suff[d]);
    if (lcpValue >= len) {
      minIndex = d + 1;
    } else {
      maxIndex = d;
    }
  }
  return maxIndex;
}
int main() {
  int n, q;
  cin >> n >> q;
  string nullstr;
  getline(cin, nullstr);
  string* input = new string[n];
  int sumLen = 0;
  for (int i = 0; i < n; i++) {
    getline(cin, input[i]);
    sumLen += input[i].length();
  }
  int strLen = sumLen + n;
  int* str = new int[strLen];
  int* origin = new int[strLen];
  int* indices = new int[n];
  int write = 0;
  for (int i = 0; i < n; i++) {
    indices[i] = write;
    for (char ch : input[i]) {
      str[write] = ch;
      origin[write] = i;
      ++write;
    }
    str[write] = 0;
    origin[write] = -1;
    ++write;
  }
  int* suff = suffixArray(str, strLen);
  int* suffOrigin = new int[strLen];
  for (int i = 0; i < strLen; i++) suffOrigin[i] = origin[suff[i]];
  int* suffInv = suffixInverseArray(suff, strLen);
  int* lcpArr = lcpArray(str, suff, suffInv, strLen);
  int* lcpSuffArr = new int[strLen];
  for (int i = 0; i < strLen; i++) {
    lcpSuffArr[i] = lcpArr[suff[i]];
  }
  LCP lcp = LCP(suffInv, lcpSuffArr, strLen);
  lowers_prefix_query lpq = lowers_prefix_query(suffOrigin, strLen);
  struct input_query {
    int index;
    int l, r, k;
    int lBound, uBound;
    int answer;
  };
  struct entry {
    int x;
    int lBound, uBound;
    int query;
    bool isLeft;
    bool operator<(entry e2) const { return x < e2.x; }
    entry() {}
    entry(int x, int lBound, int uBound, int query, bool isLeft)
        : x(x), lBound(lBound), uBound(uBound), query(query), isLeft(isLeft) {}
  };
  entry* realQueries = new entry[2 * q];
  input_query* queries = new input_query[q];
  int* lBounds = new int[n];
  int* uBounds = new int[n];
  for (int i = 0; i < n; i++) {
    lBounds[i] = uBounds[i] = -1;
  }
  for (int i = 0; i < q; i++) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    --l;
    --r;
    --k;
    queries[i].index = i;
    queries[i].l = l;
    queries[i].r = r;
    queries[i].k = k;
    if (lBounds[k] == -1) {
      lBounds[k] = lowerBound(lcp, suff, indices[k], input[k].length());
    }
    if (uBounds[k] == -1) {
      uBounds[k] = upperBound(lcp, suff, indices[k], input[k].length());
    }
    queries[i].lBound = lBounds[k];
    queries[i].uBound = uBounds[k];
    queries[i].answer = 0;
    realQueries[2 * i] =
        entry(r, queries[i].lBound, queries[i].uBound, i, false);
    realQueries[2 * i + 1] =
        entry(l - 1, queries[i].lBound, queries[i].uBound, i, true);
  }
  sort(realQueries, realQueries + 2 * q);
  lpq.reset();
  for (int i = 0; i < 2 * q; i++) {
    entry realQuery = realQueries[i];
    lpq.prepareQuery(realQuery.x);
    int answer = lpq.query(realQuery.lBound, realQuery.uBound);
    queries[realQuery.query].answer += (realQuery.isLeft ? (-1) : 1) * answer;
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", queries[i].answer);
  }
  return 0;
}