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;
int pocz[200001];
vector<int> gdzie[200000];
map<pair<int, int>, int> pos;
vector<int> pytania[200001], odpowiedzi[200001];
pair<pair<int, int>, int> zapytania[500000];
bool odw[400000];
int pre[400000], post[400000];
const int pot = 1024 * 512;
int dp[pot * 2];
void dod(int x) {
  x += pot - 1;
  while (1) {
    dp[x]++;
    if (x == 0) return;
    x = (x - 1) / 2;
  }
}
int suma(int a, int b) {
  a += pot - 1;
  b += pot - 1;
  int res = dp[a];
  if (a != b) res += dp[b];
  while ((a - 1) / 2 != (b - 1) / 2) {
    if (a % 2 == 1) res += dp[a + 1];
    if (b % 2 == 0) res += dp[b - 1];
    a = (a - 1) / 2;
    b = (b - 1) / 2;
  }
  return res;
}
struct wierz {
  pair<int, int> nast[26];
  int ojc, miejsce;
  char lit;
};
vector<wierz> drz;
int TIME;
void dfs(int x) {
  odw[x] = 1;
  pre[x] = ++TIME;
  for (int i = 0; i < 26; i++) {
    int w = drz[x].nast[i].first;
    if (w == 0 || odw[w]) continue;
    dfs(w);
  }
  post[x] = TIME;
}
string s;
int wys;
int dodaj(pair<int, int> slowo, int wsp) {
  int akt = drz.size() - 1;
  char ost;
  while (wys > wsp) {
    wys -= drz[drz[akt].ojc].nast[drz[akt].lit - 'a'].second;
    ost = drz[akt].lit;
    akt = drz[akt].ojc;
  }
  if (wys < wsp) {
    wierz nowy;
    int dziecko_nr = drz[akt].nast[ost - 'a'].first;
    char do_starego = s[drz[dziecko_nr].miejsce - wys + wsp + 1 -
                        drz[akt].nast[ost - 'a'].second];
    nowy.nast[do_starego - 'a'] =
        make_pair(dziecko_nr, drz[akt].nast[ost - 'a'].second + wys - wsp);
    nowy.ojc = akt;
    nowy.lit = ost;
    nowy.miejsce = drz[dziecko_nr].miejsce - nowy.nast[do_starego - 'a'].second;
    drz[dziecko_nr].ojc = drz.size();
    drz[akt].nast[ost - 'a'] = make_pair(drz.size(), wsp - wys);
    drz.push_back(nowy);
    wys = wsp;
    akt = drz.size() - 1;
  }
  int len = slowo.second - slowo.first + 1;
  if (wys == len) return akt;
  wierz nowy;
  drz[akt].nast[s[slowo.first + wsp] - 'a'] = make_pair(drz.size(), len - wsp);
  nowy.ojc = akt;
  nowy.lit = s[slowo.first + wsp];
  nowy.miejsce = slowo.second;
  drz.push_back(nowy);
  wys = len;
  return drz.size() - 1;
}
int H[19][200000], pot2[19];
void kmr_prep() {
  int l = s.size();
  for (int i = 0; i < l; i++) H[0][i] = s[i] - 'a';
  pot2[0] = 1;
  for (int i = 1; i <= 18; i++) {
    vector<pair<pair<int, int>, int> > tmp;
    pot2[i] = pot2[i - 1] * 2;
    for (int j = 0; j < l; j++) {
      tmp.push_back(make_pair(
          make_pair(H[i - 1][j],
                    (j + pot2[i - 1] < l) ? H[i - 1][j + pot2[i - 1]] : -1),
          j));
    }
    sort(tmp.begin(), tmp.end());
    int it = 0;
    H[i][tmp[0].second] = 0;
    for (int j = 1; j < tmp.size(); j++) {
      it += (tmp[j].first > tmp[j - 1].first);
      H[i][tmp[j].second] = it;
    }
  }
}
int wspolny(pair<int, int> s1, pair<int, int> s2) {
  int res = 0;
  for (int i = 18; i >= 0; i--) {
    if (pot2[i] > s1.second - s1.first + 1 ||
        pot2[i] > s2.second - s2.first + 1)
      continue;
    if (H[i][s1.first] == H[i][s2.first]) {
      res += pot2[i];
      s1.first += pot2[i];
      s2.first += pot2[i];
    }
  }
  return res;
}
bool comp(pair<int, int> s1, pair<int, int> s2) {
  int l1 = s1.second - s1.first + 1, l2 = s2.second - s2.first + 1, l, wyk = 0;
  l = min(l1, l2);
  while (pot2[wyk] * 2 <= l) wyk++;
  pair<int, int> a =
      make_pair(H[wyk][s1.first], H[wyk][s1.first + l - pot2[wyk]]);
  pair<int, int> b =
      make_pair(H[wyk][s2.first], H[wyk][s2.first + l - pot2[wyk]]);
  if (a > b) return 0;
  if (a < b) return 1;
  return (l1 < l2);
}
void odpowiadaj() {
  for (int i = 0; i < pytania[0].size(); i++) odpowiedzi[0].push_back(0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < gdzie[i].size(); j++) dod(pre[gdzie[i][j]]);
    for (int j = 0; j < pytania[i + 1].size(); j++) {
      int w = pytania[i + 1][j];
      odpowiedzi[i + 1].push_back(suma(pre[w], post[w]));
    }
  }
}
vector<pair<int, int> > suf;
vector<int> lcp;
int main() {
  ios_base::sync_with_stdio(0);
  int m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string str;
    pocz[i] = s.size();
    cin >> str;
    s += str;
  }
  pocz[n] = s.size();
  kmr_prep();
  for (int i = 0; i < n; i++) {
    for (int j = pocz[i]; j < pocz[i + 1]; j++)
      suf.push_back(make_pair(j, pocz[i + 1] - 1));
  }
  sort(suf.begin(), suf.end(), comp);
  for (int i = 0; i < (int)suf.size() - 1; i++)
    lcp.push_back(wspolny(suf[i], suf[i + 1]));
  wierz root;
  drz.push_back(root);
  drz.push_back(root);
  drz[0].nast[s[suf[0].first] - 'a'] =
      make_pair(1, suf[0].second - suf[0].first + 1);
  drz[1].ojc = 0;
  drz[1].lit = s[suf[0].first];
  drz[1].miejsce = suf[0].second;
  wys = suf[0].second - suf[0].first + 1;
  pos[suf[0]] = 1;
  for (int i = 1; i < suf.size(); i++) pos[suf[i]] = dodaj(suf[i], lcp[i - 1]);
  for (int i = 0; i < n; i++) {
    for (int j = pocz[i]; j < pocz[i + 1]; j++) {
      gdzie[i].push_back(pos[make_pair(j, pocz[i + 1] - 1)]);
    }
  }
  dfs(0);
  for (int i = 0; i < m; i++) {
    cin >> zapytania[i].first.first >> zapytania[i].first.second >>
        zapytania[i].second;
    pytania[zapytania[i].first.first - 1].push_back(
        gdzie[zapytania[i].second - 1][0]);
    pytania[zapytania[i].first.second].push_back(
        gdzie[zapytania[i].second - 1][0]);
  }
  for (int i = 0; i <= n; i++) {
    if (pytania[i].size() == 0) continue;
    vector<int> tmp;
    sort(pytania[i].begin(), pytania[i].end());
    tmp.push_back(pytania[i][0]);
    for (int j = 1; j < pytania[i].size(); j++) {
      if (pytania[i][j] != pytania[i][j - 1]) tmp.push_back(pytania[i][j]);
    }
    pytania[i] = tmp;
  }
  odpowiadaj();
  for (int i = 0; i < m; i++) {
    int tmp = lower_bound(pytania[zapytania[i].first.first - 1].begin(),
                          pytania[zapytania[i].first.first - 1].end(),
                          gdzie[zapytania[i].second - 1][0]) -
              pytania[zapytania[i].first.first - 1].begin();
    int res = -odpowiedzi[zapytania[i].first.first - 1][tmp];
    tmp = lower_bound(pytania[zapytania[i].first.second].begin(),
                      pytania[zapytania[i].first.second].end(),
                      gdzie[zapytania[i].second - 1][0]) -
          pytania[zapytania[i].first.second].begin();
    res += odpowiedzi[zapytania[i].first.second][tmp];
    cout << res << "\n";
  }
}