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;
int n, q, i, j, k, sz = 1, num[500005];
string s[500005];
int a[500005];
int c[500005][26], go[500005][26];
int link[500005], up[500005];
int par[500005], par_char[500005];
vector<int> isTerminal[500005], st[500005];
int Go(int v, int x);
int getLink(int v) {
  if (link[v] == -1) {
    if (v == 0 || par[v] == 0)
      link[v] = 0;
    else
      link[v] = Go(getLink(par[v]), par_char[v]);
  }
  return link[v];
}
int Go(int v, int x) {
  if (go[v][x] == -1) {
    if (c[v][x] != -1)
      go[v][x] = c[v][x];
    else {
      if (v == 0)
        go[v][x] = 0;
      else
        go[v][x] = Go(getLink(v), x);
    }
  }
  return go[v][x];
}
int getUp(int v) {
  if (up[v] == -1) {
    if (v == 0)
      up[v] = 0;
    else {
      if (isTerminal[getLink(v)].size() != 0)
        up[v] = getLink(v);
      else
        up[v] = getUp(getLink(v));
    }
  }
  return up[v];
}
void build(int id) {
  fill(c[id], c[id] + 26, -1);
  fill(go[id], go[id] + 26, -1);
  up[id] = link[id] = -1;
  par[id] = par_char[id] = 0;
}
void add(string s, int id) {
  int i, v = 0, x;
  for (i = 0; i < s.size(); i++) {
    x = s[i] - 'a';
    if (c[v][x] == -1) {
      build(sz);
      par[sz] = v;
      par_char[sz] = x;
      c[v][x] = sz++;
    }
    v = c[v][x];
    st[v].push_back(id);
  }
  num[id] = v;
  isTerminal[v].push_back(id);
}
vector<int> g[500005];
int in[500005], out[500005], timer;
void dfs(int v) {
  int i, to;
  in[v] = timer;
  for (i = 0; i < st[v].size(); i++) a[timer++] = st[v][i];
  for (i = 0; i < g[v].size(); i++) {
    to = g[v][i];
    dfs(to);
  }
  out[v] = timer - 1;
}
vector<int> t[500005 * 4];
void build(int v, int tl, int tr) {
  int m = (tl + tr) / 2;
  if (tl == tr) {
    t[v].push_back(a[tl]);
    return;
  }
  build(v * 2, tl, m);
  build(v * 2 + 1, m + 1, tr);
  merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(),
        t[v * 2 + 1].end(), back_inserter(t[v]));
}
int get(int v, int tl, int tr, int l, int r, int a, int b) {
  int m = (tl + tr) / 2;
  if (l > r) return 0;
  if (tl == l && tr == r)
    return upper_bound(t[v].begin(), t[v].end(), b) -
           upper_bound(t[v].begin(), t[v].end(), a - 1);
  return get(v * 2, tl, m, l, min(r, m), a, b) +
         get(v * 2 + 1, m + 1, tr, max(l, m + 1), r, a, b);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie();
  cin >> n >> q;
  build(0);
  for (i = 0; i < n; i++) {
    cin >> s[i];
    add(s[i], i);
  }
  for (i = 1; i < sz; i++) g[getLink(i)].push_back(i);
  dfs(0);
  build(1, 0, timer - 1);
  while (q--) {
    int l, r;
    cin >> l >> r >> k;
    l--;
    r--;
    k--;
    cout << get(1, 0, timer - 1, in[num[k]], out[num[k]], l, r) << endl;
  }
  return 0;
}