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 int MAXN = 5e5 + 51;
struct Edge {
  long long int to, prev;
};
struct Query {
  long long int l, r, kk, id;
};
struct BIT {
  long long int sz;
  long long int num[MAXN];
  BIT() { memset(num, 0, sizeof(num)); }
  inline void add(long long int pos, long long int val) {
    for (; pos <= sz; pos += pos & -pos) {
      num[pos] += val;
    }
  }
  inline long long int query(long long int pos) {
    long long int res = 0;
    for (; pos; pos -= pos & -pos) {
      res += num[pos];
    }
    return res;
  }
};
Edge ed[MAXN];
Query qry[MAXN];
BIT bit;
long long int n, tot, qcnt, dfn;
long long int last[MAXN], f[MAXN], l[MAXN], r[MAXN], dp[MAXN], res[MAXN];
string str[MAXN];
inline long long int read() {
  register long long int num = 0, neg = 1;
  register char ch = getchar();
  while (!isdigit(ch) && ch != '-') {
    ch = getchar();
  }
  if (ch == '-') {
    neg = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    num = (num << 3) + (num << 1) + (ch - '0');
    ch = getchar();
  }
  return num * neg;
}
namespace ACAutomaton {
const long long int sigmaSize = 26;
queue<long long int> q;
struct ACAutomaton {
  long long int trie[MAXN][sigmaSize], fail[MAXN], cnt;
  inline void insert(string str, long long int ind) {
    long long int length = str.length(), cur = 0, num;
    for (register int i = 0; i < length; i++) {
      num = str[i] - 'a';
      if (!trie[cur][num]) {
        trie[cur][num] = ++cnt;
      }
      cur = trie[cur][num];
    }
    f[ind] = cur;
  }
  inline void create() {
    long long int top;
    for (register int i = 0; i < sigmaSize; i++) {
      if (trie[0][i]) {
        fail[trie[0][i]] = 0;
        q.push(trie[0][i]);
      }
    }
    while (!q.empty()) {
      top = q.front(), q.pop();
      for (register int i = 0; i < sigmaSize; i++) {
        if (trie[top][i]) {
          fail[trie[top][i]] = trie[fail[top]][i], q.push(trie[top][i]);
        } else {
          trie[top][i] = trie[fail[top]][i];
        }
      }
    }
  }
};
}  // namespace ACAutomaton
ACAutomaton::ACAutomaton AC;
inline void addEdge(long long int from, long long int to) {
  ed[++tot].to = to;
  ed[tot].prev = last[from];
  last[from] = tot;
}
inline bool cmp(Query x, Query y) { return x.r < y.r; }
inline bool cmp2(Query x, Query y) { return x.l < y.l; }
inline void dfs(long long int node) {
  l[node] = ++dfn;
  for (register int i = last[node]; i; i = ed[i].prev) {
    dfs(ed[i].to);
  }
  r[node] = dfn;
}
inline void calc() {
  sort(qry + 1, qry + qcnt + 1, cmp);
  long long int ptr = 1, length, cur;
  for (register int i = 1; i <= n; i++) {
    length = str[i].length(), cur = 0;
    for (register int j = 0; j < length; j++) {
      cur = AC.trie[cur][str[i][j] - 'a'], bit.add(l[cur], 1);
    }
    while (ptr <= qcnt && qry[ptr].r == i) {
      res[qry[ptr].id] +=
          bit.query(r[f[qry[ptr].kk]]) - bit.query(l[f[qry[ptr].kk]] - 1);
      ptr++;
    }
  }
}
inline void calc2() {
  memset(bit.num, 0, sizeof(bit.num));
  sort(qry + 1, qry + qcnt + 1, cmp2);
  long long int ptr = 1, length, cur;
  while (ptr <= qcnt && qry[ptr].l == 0) {
    ptr++;
  }
  for (register int i = 1; i <= n; i++) {
    length = str[i].length(), cur = 0;
    for (register int j = 0; j < length; j++) {
      cur = AC.trie[cur][str[i][j] - 'a'], bit.add(l[cur], 1);
    }
    while (ptr <= qcnt && qry[ptr].l == i) {
      res[qry[ptr].id] -=
          (bit.query(r[f[qry[ptr].kk]]) - bit.query(l[f[qry[ptr].kk]] - 1));
      ptr++;
    }
  }
}
int main() {
  n = read(), qcnt = read();
  for (register int i = 1; i <= n; i++) {
    cin >> str[i], AC.insert(str[i], i);
  }
  AC.create();
  for (register int i = 1; i <= AC.cnt; i++) {
    addEdge(AC.fail[i], i);
  }
  dfs(0), bit.sz = dfn;
  for (register int i = 1; i <= qcnt; i++) {
    qry[i].l = read() - 1, qry[i].r = read(), qry[i].kk = read(), qry[i].id = i;
  }
  calc(), calc2();
  for (register int i = 1; i <= qcnt; i++) {
    printf("%lld\n", res[i]);
  }
}