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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 200000;
const int MAXSUMLEN = 200000;
const int MAXT = MAXSUMLEN + 1;
const int MAXQ = 500000;
const int ASIZE = 26;
typedef struct Q {
  int x, sgn, l, r, idx;
} Q;
int n, nq;
int off[MAXN], len[MAXN];
char s[MAXSUMLEN + 1];
int nt, root;
int tnxt[MAXT][ASIZE];
int lst[MAXN];
int f[MAXT];
int q[MAXT], qhead, qtail;
int ufst[MAXT], unxt[MAXT];
int np;
int pfst[MAXT], pnxt[MAXSUMLEN], pidx[MAXSUMLEN];
int na;
int a[MAXSUMLEN];
int la[MAXT], ra[MAXT];
int afst[MAXN], anxt[MAXSUMLEN];
int ql[MAXQ], qr[MAXQ], qk[MAXQ];
int qlfst[MAXN], qlnxt[MAXQ];
int qrfst[MAXN], qrnxt[MAXQ];
int ret[MAXQ];
int fw[MAXN + 1];
int create() {
  for (int i = (0); i < (ASIZE); ++i) tnxt[nt][i] = -1;
  pfst[nt] = -1;
  return nt++;
}
void build(int i) {
  int at = root;
  for (int j = (0); j < (len[i]); ++j) {
    int x = s[off[i] + j] - 'a';
    if (tnxt[at][x] == -1) tnxt[at][x] = create();
    at = tnxt[at][x];
    pnxt[np] = pfst[at];
    pfst[at] = np;
    pidx[np] = i;
    ++np;
  }
  lst[i] = at;
}
void ahoc() {
  qhead = qtail = 0;
  f[root] = root;
  q[qhead++] = root;
  while (qtail < qhead) {
    int at = q[qtail++];
    for (int i = (0); i < (ASIZE); ++i)
      if (tnxt[at][i] != -1) {
        int to = tnxt[at][i];
        q[qhead++] = to;
        f[to] = f[at];
        while (f[to] != root && tnxt[f[to]][i] == -1) f[to] = f[f[to]];
        if (at != root && tnxt[f[to]][i] != -1) f[to] = tnxt[f[to]][i];
      }
  }
}
void makea(int at) {
  la[at] = na;
  for (int y = pfst[at]; y != -1; y = pnxt[y]) a[na++] = pidx[y];
  for (int x = ufst[at]; x != -1; x = unxt[x]) makea(x);
  ra[at] = na;
}
void printt(int at, int d = 0) {
  for (int i = (0); i < (ASIZE); ++i)
    if (tnxt[at][i] != -1) {
      int to = tnxt[at][i];
      for (int j = (0); j < (d); ++j) printf("  ");
      printf("%d=%c", to, 'a' + i);
      for (int y = pfst[to]; y != -1; y = pnxt[y]) printf(" %d", pidx[y]);
      printf(" (%d)\n", f[to]);
      printt(to, d + 1);
    }
}
void printu(int at, int d = 0) {
  for (int x = ufst[at]; x != -1; x = unxt[x]) {
    int to = x;
    for (int j = (0); j < (d); ++j) printf("  ");
    printf("%d=%c", to, '?');
    for (int y = pfst[to]; y != -1; y = pnxt[y]) printf(" %d", pidx[y]);
    printf(" (%d)\n", f[to]);
    printu(to, d + 1);
  }
}
void fwinc(int x) {
  while (x <= MAXN) {
    fw[x]++;
    x += x & -x;
  }
}
int fwget(int x) {
  int ret = 0;
  while (x > 0) {
    ret += fw[x];
    x -= x & -x;
  }
  return ret;
}
int calc(int i) { return fwget(ra[lst[i]]) - fwget(la[lst[i]]); }
void input() {
  scanf("%d%d", &n, &nq);
  for (int i = (0); i < (n); ++i) {
    off[i] = i == 0 ? 0 : off[i - 1] + len[i - 1];
    scanf("%s", s + off[i]);
    len[i] = strlen(s + off[i]);
  }
  s[off[n - 1] + len[n - 1]] = '\0';
  for (int qi = (0); qi < (nq); ++qi) {
    scanf("%d%d%d", &ql[qi], &qr[qi], &qk[qi]);
    --ql[qi], --qr[qi], --qk[qi];
  }
}
void solve() {
  nt = np = 0;
  root = create();
  for (int i = (0); i < (n); ++i) build(i);
  ahoc();
  for (int i = (0); i < (nt); ++i) ufst[i] = -1;
  unxt[root] = -1;
  for (int i = (0); i < (nt); ++i)
    if (i != root) {
      unxt[i] = ufst[f[i]];
      ufst[f[i]] = i;
    }
  na = 0;
  makea(root);
  for (int i = (0); i < (n); ++i) afst[i] = -1;
  for (int i = (0); i < (na); ++i) anxt[i] = afst[a[i]], afst[a[i]] = i;
  for (int i = (0); i < (n); ++i) qlfst[i] = qrfst[i] = -1;
  for (int qi = (0); qi < (nq); ++qi) {
    qlnxt[qi] = qlfst[ql[qi]], qlfst[ql[qi]] = qi;
    qrnxt[qi] = qrfst[qr[qi]], qrfst[qr[qi]] = qi;
  }
  memset(fw, 0, sizeof(fw));
  memset(ret, 0, sizeof(ret));
  for (int i = (0); i < (n); ++i) {
    for (int x = qlfst[i]; x != -1; x = qlnxt[x]) ret[x] -= calc(qk[x]);
    for (int x = afst[i]; x != -1; x = anxt[x]) fwinc(x + 1);
    for (int x = qrfst[i]; x != -1; x = qrnxt[x]) ret[x] += calc(qk[x]);
  }
}
void run() {
  input();
  solve();
  for (int qi = (0); qi < (nq); ++qi) printf("%d\n", ret[qi]);
}
void test() {
  n = 441;
  nq = 11;
  for (int i = (0); i < (MAXSUMLEN); ++i) s[i] = 'a' + rand() % 26;
  s[MAXSUMLEN] = '\0';
  while (true) {
    off[0] = 0;
    for (int i = (1); i < (n); ++i) off[i] = rand() % MAXSUMLEN;
    sort(off, off + n);
    bool ok = true;
    for (int i = (1); i < (n); ++i)
      if (off[i] == off[i - 1]) ok = false;
    if (ok) break;
  }
  for (int i = (0); i < (n - 1); ++i) len[i] = off[i + 1] - off[i];
  len[n - 1] = MAXSUMLEN - off[n - 1];
  for (int i = (0); i < (nq); ++i) {
    ql[i] = rand() % n, qr[i] = rand() % n, qk[i] = rand() % n;
    if (ql[i] > qr[i]) swap(ql[i], qr[i]);
  }
  solve();
  for (int qi = (0); qi < (nq); ++qi) printf("%d\n", ret[qi]);
}
int main() {
  run();
  return 0;
}