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 mod = 1e9 + 123;
const int base = 510;
const int N = 200005;
const int M = 500005;
struct Query {
  int id, l, r, v;
  Query(int id, int l, int r, int v) : id(id), l(l), r(r), v(v) {}
};
int n, q;
int pos[N];
int pw[N];
int lg2[N];
int res[M];
int bit[N];
int rmq[20][N];
vector<string> S;
vector<vector<int> > Hash;
vector<pair<int, int> > sa;
vector<Query> queries[N];
int getHash(int id, int l, int r) {
  int ret = Hash[id][r] - 1LL * Hash[id][l - 1] * pw[r - l + 1] % mod;
  return (ret < 0) ? ret + mod : ret;
}
int find(pair<int, int> x, pair<int, int> y) {
  int mx_x = S[x.first].size() - x.second + 1;
  int mx_y = S[y.first].size() - y.second + 1;
  int l = 0, r = min(mx_x, mx_y);
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (getHash(x.first, x.second, x.second + mid - 1) ==
        getHash(y.first, y.second, y.second + mid - 1))
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}
bool cmp(pair<int, int> x, pair<int, int> y) {
  int mx_x = S[x.first].size() - x.second + 1;
  int mx_y = S[y.first].size() - y.second + 1;
  int tmp = find(x, y);
  if (tmp == min(mx_x, mx_y)) return mx_x < mx_y;
  return S[x.first][x.second + tmp - 1] < S[y.first][y.second + tmp - 1];
}
int getRmq(int l, int r) {
  if (l == r) {
    return S[sa[l].first].size() - sa[l].second + 1;
  }
  r--;
  int k = lg2[r - l + 1];
  return min(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
void upd(int x) {
  for (; x < N; x += x & -x) bit[x]++;
}
int get(int x) {
  int ret = 0;
  for (; x > 0; x -= x & -x) ret += bit[x];
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> q;
  pw[0] = 1;
  for (int i = 1; i < N; ++i) pw[i] = 1LL * pw[i - 1] * base % mod;
  for (int i = 2; i < N; ++i) lg2[i] = lg2[i >> 1] + 1;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    S.push_back(s);
    int sz = s.size();
    vector<int> tmp;
    tmp.assign(sz + 1, 0);
    for (int j = 1; j <= sz; ++j) {
      tmp[j] = (1LL * tmp[j - 1] * base + s[j - 1] - 'a' + 1) % mod;
    }
    Hash.push_back(tmp);
    for (int j = 1; j <= sz; ++j) sa.push_back(pair<int, int>(i, j));
  }
  sort(sa.begin(), sa.end(), cmp);
  int sz = sa.size();
  for (int i = 0; i < sz; ++i) {
    if (sa[i].second == 1) pos[sa[i].first] = i;
  }
  for (int i = 0; i < (sz - 1); ++i) {
    rmq[0][i] = find(sa[i], sa[i + 1]);
  }
  for (int i = 1; i <= 19; ++i) {
    for (int j = 0; j + (1 << i) - 1 < (sz - 1); ++j) {
      rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int i = 0; i < q; ++i) {
    int l, r, x;
    cin >> l >> r >> x;
    l--, r--, x--;
    int szx = S[x].size();
    x = pos[x];
    int L, R, low, high;
    low = 0, high = x;
    while (low < high) {
      int mid = (low + high) >> 1;
      if (getRmq(mid, x) == szx)
        high = mid;
      else
        low = mid + 1;
    }
    L = low;
    low = x, high = sz - 1;
    while (low < high) {
      int mid = (low + high + 1) >> 1;
      if (getRmq(x, mid) == szx)
        low = mid;
      else
        high = mid - 1;
    }
    R = low;
    if (L) queries[L - 1].push_back(Query(i, l + 1, r + 1, -1));
    queries[R].push_back(Query(i, l + 1, r + 1, 1));
  }
  for (int i = 0; i < sz; ++i) {
    upd(sa[i].first + 1);
    for (auto j : queries[i]) {
      res[j.id] += (get(j.r) - get(j.l - 1)) * j.v;
    }
  }
  for (int i = 0; i < q; ++i) cout << res[i] << '\n';
}