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 maxN = 2e5 + 9, maxV = 5e5, MOD = 1e9 + 7, lg = 20, LIM = 100;
vector<pair<pair<int, int>, int> > quers[maxN];
int ans[maxV], trie[maxN][26], tc = 1, tpar[maxN];
int asoc[maxN];
vector<int> adj[maxN], inde[maxN];
string arr[maxN];
int n, q, ct = 1;
void executebfs() {
  queue<int> q;
  for (int i = 0; i < 26; i++) {
    int ne = trie[0][i];
    if (ne) {
      adj[0].push_back(ne);
      q.push(ne);
    }
  }
  while (q.size()) {
    int cr = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      int ne = trie[cr][i], pa;
      if (!ne) continue;
      for (pa = tpar[cr]; pa > 0 && !trie[pa][i]; pa = tpar[pa])
        ;
      tpar[ne] = trie[pa][i];
      adj[tpar[ne]].push_back(ne);
      q.push(ne);
    }
  }
  for (int i = 0, j, c; i < n; i++) {
    for (c = 0, j = 0; j < arr[i].size(); j++) {
      if (!trie[c][arr[i][j] - 'a']) trie[c][arr[i][j] - 'a'] = tc++;
      c = trie[c][arr[i][j] - 'a'];
    }
    asoc[i] = c;
  }
}
int sz[maxN], bg[maxN], fen[maxN];
void update(int w, int x) {
  for (w = n - w; w <= n; w += w & -w) fen[w] += x;
}
int query(int w) {
  int ret = 0;
  for (w = n - w; w > 0; w -= w & -w) ret += fen[w];
  return ret;
}
struct Node {
  Node *le, *ri;
  int vl;
  Node() {}
  Node(int vl, Node *le, Node *ri) : vl(vl), le(le), ri(ri) {}
} repo[maxN * 50], *trs[maxN], *null;
int repc;
Node *newNode(int vl, Node *le, Node *ri) {
  return &(repo[repc++] = Node(vl, le, ri));
}
Node *newNode(Node *le, Node *ri) {
  return &(repo[repc++] = Node(le->vl + ri->vl, le, ri));
}
Node *update(Node *nd, int l, int r, int w) {
  if (l <= w && w < r) {
    if (l + 1 == r) return newNode(nd->vl + 1, null, null);
    int m = (l + r) / 2;
    return newNode(update(nd->le, l, m, w), update(nd->ri, m, r, w));
  }
  return nd;
}
int query(Node *nd, int u, int v, int l, int r) {
  if (r <= u || v <= l) return 0;
  if (u <= l && r <= v) return nd->vl;
  int m = (l + r) / 2;
  return query(nd->le, u, v, l, m) + query(nd->ri, u, v, m, r);
}
int elm;
void dfs(int nd) {
  int strt = ++elm;
  trs[strt] = trs[strt - 1];
  for (int el : inde[nd]) trs[strt] = update(trs[strt], 0, n, el);
  for (int sn : adj[nd]) dfs(sn);
  for (pair<pair<int, int>, int> el : quers[nd])
    ans[el.second] =
        query(trs[elm], el.first.first, el.first.second, 0, n) -
        query(trs[strt - 1], el.first.first, el.first.second, 0, n);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  null = newNode(0, NULL, NULL);
  trs[0] = null->le = null->ri = null;
  cin >> n >> q;
  for (int i = 0, j, c; i < n; i++) {
    cin >> arr[i];
    for (c = 0, j = 0; j < arr[i].size(); j++) {
      if (!trie[c][arr[i][j] - 'a']) trie[c][arr[i][j] - 'a'] = tc++;
      c = trie[c][arr[i][j] - 'a'];
    }
  }
  executebfs();
  for (int i = 0; i < q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    k--, l--;
    quers[asoc[k]].push_back(
        pair<pair<int, int>, int>(pair<int, int>(l, r), i));
  }
  for (int i = 0; i < n; i++) {
    string st = arr[i];
    for (int j = 0, c = 0; j < st.size(); j++) {
      while (c > 0 && !trie[c][st[j] - 'a']) c = tpar[c];
      c = trie[c][st[j] - 'a'];
      if (c) inde[c].push_back(i);
    }
  }
  dfs(0);
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}