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 INF = 1 << 28;
const long long LINF = 1ll << 61;
inline long long getnum() {
  register long long r = 0;
  register bool ng = 0;
  register char c;
  c = getchar();
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  if (c == '-') ng = 1, c = getchar();
  while (c != ' ' && c != '\n') r = r * 10 + c - '0', c = getchar();
  if (ng) r = -r;
  return r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline void putsp() { putchar(' '); }
inline void putendl() { putchar('\n'); }
int n, q, pos[400111], sa[400111], lcp[400111], L[400111], R[400111], sn;
char s[400111];
int ans[500111], sz[400111];
vector<pair<int, int> > query[400111];
int tmp[400111], rk[400111];
int sak;
bool cmp2(int x, int y) {
  if (rk[x] != rk[y])
    return rk[x] < rk[y];
  else {
    int t1 = x + sak <= sn ? rk[x + sak] : -1;
    int t2 = y + sak <= sn ? rk[y + sak] : -1;
    return t1 < t2;
  }
}
vector<int> buk[400111];
void initsa() {
  for (int i = 0; i <= sn; i++) {
    sa[i] = i;
    rk[i] = i < sn ? s[i] : -1;
  }
  for (int i = 1; i <= sn; i *= 2) {
    sak = i;
    for (int j = 0; j <= 400011; j++) buk[j].clear();
    for (int j = 0; j <= sn; j++)
      buk[(sa[j] + sak <= sn ? rk[sa[j] + sak] : -1) + 1].push_back(sa[j]);
    int t = 0;
    for (int j = 0; j <= 400011; j++)
      for (int k = 0; k < buk[j].size(); k++) sa[t++] = buk[j][k];
    for (int j = 0; j <= 400011; j++) buk[j].clear();
    for (int j = 0; j <= sn; j++) buk[rk[sa[j]] + 1].push_back(sa[j]);
    t = 0;
    for (int j = 0; j <= 400011; j++)
      for (int k = 0; k < buk[j].size(); k++) sa[t++] = buk[j][k];
    tmp[sa[0]] = 0;
    for (int j = 1; j <= sn; j++) {
      tmp[sa[j]] = cmp2(sa[j - 1], sa[j]) + tmp[sa[j - 1]];
    }
    for (int j = 0; j <= sn; j++) {
      rk[j] = tmp[j];
    }
  }
  for (int i = 0; i <= sn; i++) rk[sa[i]] = i;
  lcp[0] = 0;
  int len = 0;
  for (int i = 0; i < sn; i++) {
    if (len > 0) len--;
    int k = sa[rk[i] - 1];
    while (i + len < sn && k + len < sn && s[i + len] == s[k + len]) len++;
    lcp[rk[i] - 1] = len;
  }
}
struct STtable {
  int a[400111][23];
  int pow2[400111];
  void init(int size) {
    int base = 0;
    for (int i = 1; i <= 400100; i++) {
      if ((1 << (base + 1)) <= i) base++;
      pow2[i] = base;
    }
    memset(a, 0, sizeof(a));
    for (int i = 0; i < size; i++) a[i][0] = lcp[i];
    for (int k = 1; k < 23; k++) {
      for (int i = 0; i < size - (1 << k) + 1; i++) {
        a[i][k] = min(a[i][k - 1], a[i + (1 << (k - 1))][k - 1]);
      }
    }
  }
  int query(int l, int r) {
    return min(a[l][pow2[r - l + 1]],
               a[r - (1 << pow2[r - l + 1]) + 1][pow2[r - l + 1]]);
  }
} stt;
struct BIT {
  int a[400111];
  BIT() { memset(a, 0, sizeof(a)); }
  void add(int id) {
    while (id <= 400011) {
      a[id]++;
      id += id & (-id);
    }
  }
  int query(int id) {
    int ans = 0;
    while (id > 0) {
      ans += a[id];
      id -= id & (-id);
    }
    return ans;
  }
} bit;
int main() {
  n = getnum(), q = getnum();
  for (int i = 1; i <= n; i++) {
    char c;
    while ((c = getchar()) != '\n') s[sn++] = c, sz[i]++;
    pos[i] = sn;
    s[sn++] = 1;
  }
  pos[0] = -1;
  initsa();
  stt.init(sn);
  for (int i = 1; i <= n; i++) {
    int cur = rk[pos[i - 1] + 1];
    int p = cur;
    for (int j = 21; j >= 0; j--) {
      if (p - (1 << j) >= 0 && stt.query(p - (1 << j), cur - 1) >= sz[i]) {
        p -= 1 << j;
      }
    }
    L[i] = p;
    p = cur;
    for (int j = 21; j >= 0; j--) {
      if (p + (1 << j) <= sn && stt.query(cur, p + (1 << j) - 1) >= sz[i]) {
        p += 1 << j;
      }
    }
    R[i] = p;
  }
  for (int i = 1; i <= q; i++) {
    int l, r, k;
    l = getnum(), r = getnum(), k = getnum();
    query[R[k]].push_back(make_pair(pos[r] - 1, i));
    if (pos[l - 1] > 0) query[R[k]].push_back(make_pair(-(pos[l - 1]), i));
    if (L[k] > 0) {
      query[L[k] - 1].push_back(make_pair(-(pos[r] - 1), i));
      if (pos[l - 1] > 0) query[L[k] - 1].push_back(make_pair(pos[l - 1], i));
    }
  }
  for (int i = 0; i <= sn; i++) {
    bit.add(sa[i] + 1);
    for (int j = 0; j < query[i].size(); j++) {
      int tmp, x = query[i][j].first;
      if (x < 0)
        x = -x, tmp = -1;
      else
        tmp = 1;
      ans[query[i][j].second] += tmp * bit.query(x + 1);
    }
  }
  for (int i = 1; i <= q; i++) {
    putnum(ans[i]), putsp(), putendl();
  }
  return 0;
}