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 = 400007;
const int maxq = 500007;
char s[maxn];
int len, n, pos[maxn], q, id[maxn], slen[maxn];
int sa[maxn], tsa[maxn], ra[maxn], tra[maxn], cnt[maxn], pre[maxn], lcp[maxn],
    plcp[maxn], rev_sa[maxn];
int fra(int i) { return (i <= len) ? ra[i] : 0; }
int L[maxn], R[maxn], mys[maxn];
int BIT[maxn];
struct query {
  int id, i, k, sign, pos;
};
vector<int> pos_by_id[maxn];
vector<query> qlist;
bool cmp(const query &a, const query &b) { return a.i < b.i; }
int ans[maxq];
void update(int i, int v) {
  for (; i <= len; i += i & (-i)) BIT[i] += v;
}
int get(int i) {
  int res = 0;
  for (; i > 0; i -= i & (-i)) res += BIT[i];
  return res;
}
void sort(int k) {
  int maxv = max(300, len);
  for (int i = 0; i <= maxv; ++i) cnt[i] = 0;
  for (int i = 1; i <= len; ++i) cnt[fra(sa[i] + k)]++;
  for (int i = 0, sum = 0, tmp; i <= maxv; ++i) {
    tmp = sum;
    sum += cnt[i];
    cnt[i] = tmp;
  }
  for (int i = 1; i <= len; ++i) tsa[++cnt[fra(sa[i] + k)]] = sa[i];
  for (int i = 1; i <= len; ++i) sa[i] = tsa[i];
}
void constructSA() {
  for (int i = 1; i <= len; ++i) {
    sa[i] = i;
    ra[i] = s[i];
  }
  for (int k = 1; k < len; k *= 2) {
    sort(k);
    sort(0);
    tra[sa[1]] = 1;
    int r = 1;
    for (int i = 2; i <= len; ++i) {
      if (ra[sa[i]] != ra[sa[i - 1]] || fra(sa[i] + k) != fra(sa[i - 1] + k))
        ++r;
      tra[sa[i]] = r;
    }
    for (int i = 1; i <= len; ++i) ra[i] = tra[i];
  }
  pre[sa[1]] = -1;
  for (int i = 2; i <= len; ++i) pre[sa[i]] = sa[i - 1];
  int x = 0;
  for (int i = 1; i <= len; ++i) {
    if (pre[i] == -1) {
      plcp[i] = 0;
      x = 0;
      continue;
    }
    while (i + x <= len && pre[i] + x <= len && s[i + x] == s[pre[i] + x] &&
           s[i + x] != '@')
      ++x;
    plcp[i] = x;
    x = max(0, x - 1);
  }
  for (int i = 1; i <= len; ++i) lcp[i] = plcp[sa[i]];
}
int main() {
  len = 0;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s + len + 1);
    int len2 = strlen(s + len + 1);
    pos[i] = len + 1;
    for (int j = len + 1; j <= len + len2; ++j) id[j] = i;
    len += len2 + 1;
    slen[i] = len2;
    s[len] = '@';
  }
  constructSA();
  for (int i = 1; i <= len; ++i) rev_sa[sa[i]] = i;
  int last = 0;
  mys[0] = 0;
  for (int i = 1; i <= len; ++i) {
    while (last > 0 && lcp[mys[last]] >= lcp[i]) --last;
    L[i] = mys[last];
    mys[++last] = i;
  }
  mys[0] = len + 1;
  last = 0;
  for (int i = len; i >= 1; --i) {
    while (last > 0 && lcp[mys[last]] >= lcp[i]) --last;
    R[i] = mys[last];
    mys[++last] = i;
  }
  for (int i = 1; i <= len; ++i)
    if (id[sa[i]] != 0) pos_by_id[id[sa[i]]].push_back(i);
  for (int i = 1; i <= q; ++i) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    query q1, q2;
    q1.id = q2.id = i;
    q1.i = l - 1;
    q2.i = r;
    q1.sign = -1;
    q2.sign = 1;
    q1.pos = q2.pos = rev_sa[pos[k]];
    q1.k = q2.k = k;
    qlist.push_back(q1);
    qlist.push_back(q2);
  }
  sort(qlist.begin(), qlist.end(), cmp);
  int it = 1;
  memset(ans, 0, sizeof(ans));
  for (int i = 0; i < int(qlist.size()); ++i) {
    query q = qlist[i];
    while (it <= q.i) {
      for (int j = 0; j < int(pos_by_id[it].size()); ++j)
        update(pos_by_id[it][j], 1);
      ++it;
    }
    int l = q.pos - 1;
    int r = q.pos;
    if (lcp[q.pos] >= slen[q.k]) {
      l = L[q.pos] - 1;
      r = R[q.pos] - 1;
    } else if (lcp[q.pos + 1] >= slen[q.k]) {
      l = L[q.pos + 1] - 1;
      r = R[q.pos + 1] - 1;
    }
    ans[q.id] += q.sign * (get(r) - get(l));
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}