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;
using ii = pair<int, int>;
using ll = long long;
using db = long double;
using mat = vector<vector<int>>;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int blk = 450;
vector<int> vp[blk];
string S[N];
vector<int> heavy;
int n, q;
vector<string> patterns;
vector<int> light;
vector<int> FAIL(string pat) {
  int m = pat.size();
  vector<int> F(m + 1);
  int i = 0, j = -1;
  F[0] = -1;
  while (i < m) {
    while (j >= 0 && pat[i] != pat[j]) j = F[j];
    i++, j++;
    F[i] = j;
  }
  return F;
}
int KMP_Search(string txt, string pat) {
  vector<int> F = FAIL(pat);
  int i = 0, j = 0;
  int n = txt.size(), m = pat.size();
  int ret = 0;
  while (i < n) {
    while (j >= 0 && txt[i] != pat[j]) j = F[j];
    i++, j++;
    if (j == m) j = F[j], ret++;
  }
  return ret;
}
string str;
struct trie {
  vector<ii> occ;
  trie* child[26];
  trie() { memset(child, 0, sizeof child); }
  void ins(int idx) {
    if (idx == str.size()) return;
    int cur = str[idx] - 'a';
    if (!child[cur]) child[cur] = new trie();
    child[cur]->ins(idx + 1);
  }
  void ins(int idx, int kill) {
    if (occ.empty() || occ.back().first != kill)
      occ.push_back(ii(kill, occ.empty() ? 0 : occ.back().second));
    occ.back().second++;
    if (idx == str.size()) return;
    int cur = str[idx] - 'a';
    if (!child[cur]) return;
    child[cur]->ins(idx + 1, kill);
  }
  int search(int idx, int l, int r) {
    if (idx == str.size()) {
      if (occ.empty()) return 0;
      int lo = 0, hi = occ.size() - 1;
      while (lo < hi) {
        int md = lo + (hi - lo) / 2;
        if (occ[md].first >= l)
          hi = md;
        else
          lo = md + 1;
      }
      if (occ[lo].first > r || occ[lo].first < l) return 0;
      int x = lo;
      lo = 0, hi = occ.size() - 1;
      while (lo < hi) {
        int md = lo + (hi - lo + 1) / 2;
        if (occ[md].first <= r)
          lo = md;
        else
          hi = md - 1;
      }
      int y = lo;
      int ret = occ[y].second;
      if (x) ret -= occ[x - 1].second;
      return ret;
    }
    int cur = str[idx] - 'a';
    return child[cur]->search(idx + 1, l, r);
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  trie root = trie();
  for (int i = 0; i < n; i++) {
    cin >> S[i];
    if (S[i].size() >= blk)
      heavy.push_back(i);
    else {
      str = S[i];
      root.ins(0);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < S[i].size(); j++) {
      int x = min(blk - 1, (int)S[i].size() - j);
      str = S[i].substr(j, x);
      root.ins(0, i);
    }
  }
  for (int i = 0; i < heavy.size(); i++)
    for (int j = 0; j < heavy.size(); j++) {
      vp[i].push_back(KMP_Search(S[heavy[j]], S[heavy[i]]));
      if (vp[i].size() > 1) {
        vp[i].back() += vp[i][vp[i].size() - 2];
      }
    }
  int l, r, k;
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> k;
    --l, --r, --k;
    if (S[k].size() >= blk) {
      int x = lower_bound(heavy.begin(), heavy.end(), l) - heavy.begin();
      if (x == heavy.size() || heavy[x] > r) {
        cout << 0 << '\n';
        continue;
      }
      int y = upper_bound(heavy.begin(), heavy.end(), r) - heavy.begin() - 1;
      k = lower_bound(heavy.begin(), heavy.end(), k) - heavy.begin();
      int ans = vp[k][y];
      if (x) ans -= vp[k][x - 1];
      cout << ans << '\n';
    } else {
      str = S[k];
      cout << root.search(0, l, r) << '\n';
    }
  }
  return 0;
}