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 suffix {
  int poz, s1, s2, cesir;
  bool operator<(const suffix &aux) const {
    if (s1 == aux.s1) return s2 < aux.s2;
    return s1 < aux.s1;
  }
  bool operator==(const suffix &aux) const {
    return s1 == aux.s1 && s2 == aux.s2;
  }
} v[400010];
struct query {
  int x, y, a, b, poz;
  bool operator<(const query &aux) const {
    if (b == aux.b) return a > aux.a;
    return b < aux.b;
  }
} v1[500010];
int p[20][400010], aib[200010], size[200010], poz[400010], primpoz[200010],
    sol[500010], nr, n, lognr;
char sir[400010];
int lcp(int x, int y) {
  int s = 0;
  for (int i = lognr; i >= 0 && x <= nr && y <= nr; i--)
    if (p[i][x] == p[i][y]) {
      s += 1 << i;
      x += 1 << i;
      y += 1 << i;
    }
  return s;
}
void aib_update(int i, int s) {
  for (; i <= n; i += i & (-i)) aib[i] += s;
}
int aib_query(int i) {
  int s = 0;
  for (; i > 0; i -= i & (-i)) s += aib[i];
  return s;
}
int main() {
  int m, k, maxx = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("\n%s", sir + nr + 1);
    size[i] = strlen(sir + nr + 1);
    maxx = max(maxx, size[i]);
    primpoz[i] = nr + 1;
    sir[nr + size[i] + 1] = '*';
    for (int j = nr + 1; j <= nr + size[i] + 1; j++) {
      p[0][j] = sir[j];
      v[j].poz = j;
      v[j].cesir = i;
    }
    nr += size[i] + 1;
  }
  for (lognr = 1; (1 << lognr) <= maxx; lognr++)
    ;
  for (int i = 1; i <= lognr; i++) {
    for (int j = 1; j <= nr; j++) {
      v[j].s1 = p[i - 1][v[j].poz];
      if (v[j].poz + (1 << (i - 1)) <= nr)
        v[j].s2 = p[i - 1][v[j].poz + (1 << (i - 1))];
      else
        v[j].s2 = -1;
    }
    sort(v + 1, v + 1 + nr);
    for (int j = 2; j <= nr; j++)
      if (v[j] == v[j - 1])
        p[i][v[j].poz] = p[i][v[j - 1].poz];
      else
        p[i][v[j].poz] = j;
  }
  for (int i = 1; i <= nr; i++) poz[v[i].poz] = i;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &v1[i].x, &v1[i].y, &k);
    v1[i].poz = i;
    int x = poz[primpoz[k]];
    int st = 1, dr = x;
    while (st <= dr) {
      int mid = (st + dr) / 2;
      if (lcp(v[mid].poz, v[x].poz) >= size[k])
        dr = mid - 1;
      else
        st = mid + 1;
    }
    int a = st;
    st = x;
    dr = nr;
    while (st <= dr) {
      int mid = (st + dr) / 2;
      if (lcp(v[mid].poz, v[x].poz) >= size[k])
        st = mid + 1;
      else
        dr = mid - 1;
    }
    int b = dr;
    v1[i].a = a;
    v1[i].b = b;
  }
  sort(v1 + 1, v1 + 1 + m);
  int curenta = 0, curentb = -1;
  for (int i = 1; i <= m; i++) {
    if (v1[i].a <= curenta && curentb <= v1[i].b) {
      for (int j = v1[i].a; j < curenta; j++) aib_update(v[j].cesir, 1);
      for (int j = curentb + 1; j <= v1[i].b; j++) aib_update(v[j].cesir, 1);
    } else {
      for (int j = curenta; j <= curentb; j++) aib_update(v[j].cesir, -1);
      for (int j = v1[i].a; j <= v1[i].b; j++) aib_update(v[j].cesir, 1);
    }
    curenta = v1[i].a;
    curentb = v1[i].b;
    sol[v1[i].poz] = aib_query(v1[i].y) - aib_query(v1[i].x - 1);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", sol[i]);
  return 0;
}