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;
int t1[450010], t2[450010], c[450010];
bool cmp(int *r, int a, int b, int l) {
  return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int str[], int sa[], int ran[], int hei[], int n, int m) {
  n++;
  int *x = t1, *y = t2;
  for (int i = 0; i < m; ++i) c[i] = 0;
  for (int i = 0; i < n; ++i) c[x[i] = str[i]]++;
  for (int i = 1; i < m; ++i) c[i] += c[i - 1];
  for (int i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
  for (int j = 1; j <= n; j <<= 1) {
    int p = 0;
    for (int i = n - j; i < n; ++i) y[p++] = i;
    for (int i = 0; i < n; ++i)
      if (sa[i] >= j) y[p++] = sa[i] - j;
    for (int i = 0; i < m; ++i) c[i] = 0;
    for (int i = 0; i < n; ++i) c[x[y[i]]]++;
    for (int i = 1; i < m; ++i) c[i] += c[i - 1];
    for (int i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
    swap(x, y);
    p = 1;
    x[sa[0]] = 0;
    for (int i = 1; i < n; ++i)
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    if (p >= n) break;
    m = p;
  }
  int k = 0;
  n--;
  for (int i = 0; i <= n; ++i) ran[sa[i]] = i;
  for (int i = 0; i < n; ++i) {
    if (k) k--;
    int j = sa[ran[i] - 1];
    while (str[i + k] == str[j + k]) k++;
    hei[ran[i]] = k;
  }
}
void output(int buf[]) {
  for (int i = 0; i <= 8; ++i) printf("%d%c", buf[i], i == 8 ? '\n' : ' ');
}
int hei[450010], ran[450010];
int mm[450010];
int dp[450010][20];
int r[450010], sa[450010];
char s[450010];
int st[450010], len[450010], lef[450010], rig[450010];
void init(int n) {
  mm[0] = -1;
  for (int i = 1; i <= n; ++i) {
    mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
    dp[i][0] = hei[i];
  }
  for (int j = 1; j <= mm[n]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int rmq(int x, int y) {
  int k = mm[y - x + 1];
  return min(dp[x][k], dp[y - (1 << k) + 1][k]);
}
int n, q, m, rt[450010], tot;
int lc[12001010], rc[12001010], v[12001010];
int update(int rt, int pos, int val) {
  int New = ++tot, tmp = New;
  v[New] = v[rt] + val;
  int l = 1, r = m;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (pos <= mid) {
      lc[New] = ++tot;
      rc[New] = rc[rt];
      New = lc[New];
      rt = lc[rt];
      r = mid;
    } else {
      rc[New] = ++tot;
      lc[New] = lc[rt];
      New = rc[New];
      rt = rc[rt];
      l = mid + 1;
    }
    v[New] = v[rt] + val;
  }
  return tmp;
}
int query(int L, int R, int l, int r, int y1, int y2) {
  if (y1 <= l && y2 >= r) return v[R] - v[L];
  int mid = (l + r) >> 1;
  int ans = 0;
  if (y1 <= mid) ans += query(lc[L], lc[R], l, mid, y1, y2);
  if (y2 > mid) ans += query(rc[L], rc[R], mid + 1, r, y1, y2);
  return ans;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    if (i > 1) r[m++] = 1;
    scanf("%s", s);
    len[i] = strlen(s);
    st[i] = m;
    for (int j = 0; j < len[i]; ++j) r[m++] = s[j];
  }
  r[m] = 0;
  da(r, sa, ran, hei, m, 128);
  init(m);
  for (int i = 1; i <= n; ++i) {
    int pos = ran[st[i]];
    int lb = pos, ub = m + 1;
    while (ub > lb + 1) {
      int mid = (lb + ub) >> 1;
      if (rmq(pos + 1, mid) >= len[i])
        lb = mid;
      else
        ub = mid;
    }
    rig[i] = lb;
    lb = 0, ub = pos;
    while (ub > lb + 1) {
      int mid = (lb + ub) >> 1;
      if (rmq(mid + 1, pos) >= len[i])
        ub = mid;
      else
        lb = mid;
    }
    lef[i] = ub;
  }
  for (int i = 1; i <= m; ++i) rt[i] = update(rt[i - 1], ran[i - 1], 1);
  while (q--) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", query(rt[st[l]], rt[st[r] + len[r]], 1, m, lef[k], rig[k]));
  }
  return 0;
}