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 LGMAX = 19;
const int MAX = (1 << LGMAX);
struct SparseTable {
  int table[LGMAX + 1][MAX];
  void init(int A[MAX]) {
    for (int i = 0; i < MAX; i++) table[0][i] = A[i];
    for (int s = 1; s <= LGMAX; s++)
      for (int i = 0; i <= MAX - (1 << s); i++)
        table[s][i] = min(table[s - 1][i], table[s - 1][i + (1 << (s - 1))]);
  }
  int lookup(int l, int r) {
    r++;
    int s = 31 - __builtin_clz(r - l);
    return min(table[s][l], table[s][r - (1 << s)]);
  }
};
struct SuffixArray {
  int N;
  string S;
  int sa[MAX];
  int rank[MAX];
  int height[MAX];
  SparseTable table;
  void build_sa(string S0) {
    S = S0;
    N = S.size();
    int freq[256];
    memset(freq, 0, sizeof(freq));
    for (int i = 0; i < N; i++) freq[S[i]]++;
    for (int i = 1; i < 256; i++) freq[i] += freq[i - 1];
    for (int i = N - 1; i >= 0; i--) sa[--freq[S[i]]] = i;
    rank[sa[0]] = 0;
    for (int i = 0; i < N - 1; i++) {
      if (S[sa[i]] == S[sa[i + 1]])
        rank[sa[i + 1]] = rank[sa[i]];
      else
        rank[sa[i + 1]] = i + 1;
    }
    int nxt[MAX];
    int temp[MAX];
    for (int len = 1; len < N; len *= 2) {
      for (int i = 0; i < N; i++) nxt[i] = i;
      for (int i = N - len; i < N; i++) temp[nxt[rank[i]]++] = i;
      for (int i = 0; i < N; i++)
        if (sa[i] >= len) temp[nxt[rank[sa[i] - len]]++] = sa[i] - len;
      memcpy(sa, temp, sizeof(temp));
      temp[sa[0]] = 0;
      for (int i = 0; i < N - 1; i++) {
        if (sa[i] + len < N && sa[i + 1] + len < N &&
            rank[sa[i]] == rank[sa[i + 1]] &&
            rank[sa[i] + len] == rank[sa[i + 1] + len])
          temp[sa[i + 1]] = temp[sa[i]];
        else
          temp[sa[i + 1]] = i + 1;
      }
      memcpy(rank, temp, sizeof(temp));
    }
  }
  int find_heights_lcp(int p1, int p2, int l) {
    while (p1 + l < N && p2 + l < N && S[p1 + l] == S[p2 + l]) l++;
    return l;
  }
  void find_heights() {
    int pre = 0;
    for (int i = 0; i < N; i++) {
      if (rank[i] == 0)
        height[0] = 0;
      else {
        pre = find_heights_lcp(sa[rank[i] - 1], sa[rank[i]], max(pre - 1, 0));
        height[rank[i]] = pre;
      }
    }
    table.init(height);
  }
  void init(string S0) {
    build_sa(S0);
    find_heights();
  }
  int lcp(int i, int j) {
    if (i == j) return N - i;
    return table.lookup(min(rank[i], rank[j]) + 1, max(rank[i], rank[j]));
  }
};
int N, Q;
string names[MAX];
int id[MAX];
int starts[MAX];
SuffixArray SA;
vector<pair<pair<int, int>, int> > queries[MAX];
int height[MAX];
long long ans[MAX];
struct BIT {
  long long bit[MAX];
  void insert(int x, int i) {
    i += 10;
    for (; i < MAX; i += i & -i) bit[i] += x;
  }
  long long lookup(int i) {
    long long res = 0;
    i += 10;
    for (; i > 0; i -= i & -i) res += bit[i];
    return res;
  }
};
BIT bit;
int main() {
  ios::sync_with_stdio(false);
  cin >> N >> Q;
  int total_len = 0;
  for (int i = 1; i <= N; i++) {
    cin >> names[i];
    total_len += names[i].size() + 1;
  }
  string S(total_len, '#');
  int next_id = 0;
  for (int i = 1; i <= N; i++) {
    starts[i] = next_id;
    for (int j = 0; j < names[i].size(); j++) {
      S[next_id] = names[i][j];
      id[next_id] = i;
      next_id++;
    }
    next_id++;
  }
  SA.init(S);
  for (int i = 0; i < S.size(); i++) height[SA.rank[i]] = id[i];
  for (int q = 1; q <= Q; q++) {
    int l, r, k;
    cin >> l >> r >> k;
    int m = starts[k];
    int s, t;
    {
      int low = -1, high = SA.rank[m];
      while (low + 1 < high) {
        int mid = (low + high) / 2;
        if (SA.lcp(SA.sa[mid], m) >= names[k].size())
          high = mid;
        else
          low = mid;
      }
      s = high;
    }
    {
      int low = SA.rank[m], high = S.size();
      while (low + 1 < high) {
        int mid = (low + high) / 2;
        if (SA.lcp(m, SA.sa[mid]) >= names[k].size())
          low = mid;
        else
          high = mid;
      }
      t = low;
    }
    if (s > 0) queries[s - 1].push_back(make_pair(make_pair(l, r), -q));
    queries[t].push_back(make_pair(make_pair(l, r), q));
  }
  for (int i = 0; i < S.size(); i++) {
    bit.insert(1, id[SA.sa[i]]);
    for (int j = 0; j < queries[i].size(); j++) {
      int l = queries[i][j].first.first;
      int r = queries[i][j].first.second;
      int q = queries[i][j].second;
      long long v = bit.lookup(r) - bit.lookup(l - 1);
      if (q > 0)
        ans[q] += v;
      else
        ans[-q] -= v;
    }
  }
  for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
}