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 QQ = 500007;
const int N = 400007;
int n, q, ptr, startPos[N], len[N], spos[N];
char st[N], buf[N];
int cnt[N], p[N], tp[N], pos[N], c[20][N];
int lcp[N], suffWho[N], who[N];
int mlog[N], mini[20][N];
int ansPlus[QQ], ansMinus[QQ];
void build() {
  int n = ptr;
  for (int i = 0; i < (n); ++i) ++cnt[(int)st[i]];
  for (int i = 0; i < (N); ++i) {
    if (i) cnt[i] += cnt[i - 1];
  }
  for (int i = n - 1; i >= 0; --i) p[--cnt[(int)st[i]]] = i;
  c[0][p[0]] = 0;
  for (int i = 1, cur = 0; i < n; ++i) {
    if (st[p[i - 1]] != st[p[i]]) ++cur;
    c[0][p[i]] = cur;
  }
  for (int h = 0; (1 << h) < n; ++h) {
    for (int i = 0; i < (n); ++i) tp[i] = (p[i] - (1 << h) + n) % n;
    for (int i = 0; i < (n); ++i) cnt[i] = 0;
    for (int i = 0; i < (n); ++i) ++cnt[c[h][i]];
    for (int i = 0; i < (n); ++i) {
      if (i) cnt[i] += cnt[i - 1];
    }
    for (int i = n - 1; i >= 0; --i) {
      p[--cnt[c[h][tp[i]]]] = tp[i];
    }
    c[h + 1][p[0]] = 0;
    for (int i = 1, cur = 0; i < n; ++i) {
      int m1 = (p[i - 1] + (1 << h)) % n;
      int m2 = (p[i] + (1 << h)) % n;
      if (c[h][p[i - 1]] != c[h][p[i]] || c[h][m1] != c[h][m2]) ++cur;
      c[h + 1][p[i]] = cur;
    }
  }
}
int getLcp(int i, int j) {
  int len = 0;
  for (int h = 19; h >= 0; --h) {
    if ((1 << h) <= ptr && c[h][i] == c[h][j]) {
      i += (1 << h);
      j += (1 << h);
      len += (1 << h);
    }
  }
  return len;
}
int getmin(int l, int r) {
  if (l == r) return 1 << 29;
  --r;
  int k = mlog[r - l + 1];
  return min(mini[k][l], mini[k][r - (1 << k) + 1]);
}
enum { ADD, ASK };
struct Query {
  int L, R, x;
  int *where;
  int type;
  static Query askQuery(int L, int R, int x, int *where) {
    Query ret;
    ret.L = L;
    ret.R = R;
    ret.x = x;
    ret.where = where;
    ret.type = ASK;
    return ret;
  }
  static Query addQuery(int L, int x) {
    Query ret;
    ret.L = L;
    ret.x = x;
    ret.type = ADD;
    return ret;
  }
  bool operator<(const Query &o) const {
    if (x != o.x) return x < o.x;
    return type < o.type;
  }
};
vector<Query> Q;
struct Fenwick {
  int T[N];
  void inc(int pos) {
    for (++pos; pos < N; pos += (pos & -pos)) ++T[pos];
  }
  int sum(int pos) {
    int ret = 0;
    for (++pos; pos; pos -= (pos & -pos)) ret += T[pos];
    return ret;
  }
} tree;
void solve() {
  scanf("%d%d", &n, &q);
  memset(who, -1, sizeof who);
  for (int i = 0; i < (n); ++i) {
    scanf("%s", buf);
    len[i] = strlen(buf);
    startPos[i] = ptr;
    for (int j = 0; j < (len[i]); ++j) {
      st[ptr] = buf[j];
      who[ptr] = i;
      ++ptr;
    }
    st[ptr++] = '$';
  }
  st[ptr++] = '#';
  st[ptr] = 0;
  build();
  for (int i = 0; i < (ptr - 1); ++i) {
    lcp[i] = getLcp(p[i], p[i + 1]);
  }
  for (int i = 0; i < (ptr); ++i) suffWho[i] = who[p[i]];
  for (int i = 0; i < (ptr); ++i) pos[p[i]] = i;
  for (int i = 0; i < (n); ++i) spos[i] = pos[startPos[i]];
  for (int i = 0; i < (ptr - 1); ++i) mini[0][i] = lcp[i];
  for (int k = 0; k < (19); ++k) {
    for (int i = 0; i < (ptr - 1); ++i) {
      if (i + (1 << (k + 1)) - 1 >= ptr - 1) continue;
      mini[k + 1][i] = min(mini[k][i], mini[k][i + (1 << k)]);
    }
  }
  mlog[1] = 0;
  for (int i = 2; i < N; ++i) mlog[i] = 1 + mlog[i >> 1];
  for (int iter = 0; iter < (q); ++iter) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    --l, --r, --k;
    int pos = spos[k];
    int len = ::len[k];
    int lo = 0;
    int hi = pos;
    while (lo < hi) {
      int mi = (lo + hi) / 2;
      if (getmin(mi, pos) >= len)
        hi = mi;
      else
        lo = mi + 1;
    }
    int L = lo;
    lo = pos;
    hi = ptr - 1;
    while (lo < hi) {
      int mi = (lo + hi + 1) / 2;
      if (getmin(pos, mi) >= len)
        lo = mi;
      else
        hi = mi - 1;
    }
    int R = lo;
    Q.push_back(Query::askQuery(L, R, r, &ansPlus[iter]));
    if (l > 0) Q.push_back(Query::askQuery(L, R, l - 1, &ansMinus[iter]));
  }
  for (int i = 0; i < (ptr); ++i) {
    if (suffWho[i] != -1) Q.push_back(Query::addQuery(i, suffWho[i]));
  }
  sort((Q).begin(), (Q).end());
  for (auto q : Q) {
    if (q.type == ADD)
      tree.inc(q.L);
    else {
      *(q.where) += tree.sum(q.R) - tree.sum(q.L - 1);
    }
  }
  for (int i = 0; i < (q); ++i) {
    printf("%d\n", ansPlus[i] - ansMinus[i]);
  }
}
void testGen() {
  FILE *f = fopen("input.txt", "w");
  fclose(f);
}
int main() {
  cerr << fixed;
  cerr.precision(3);
  cout << fixed;
  cout.precision(9);
  solve();
  return 0;
}