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 ALP = 256;
const int MAXL = 410010;
const int MAXV = 2 * MAXL;
map<char, int> go[MAXV], link[MAXV];
int par[MAXV], pos[MAXV], len[MAXV];
int SZ;
string in;
void init() {
  SZ = 2;
  len[1] = 1;
  pos[1] = par[1] = 0;
  for (int i = 0; i < ALP; ++i) link[0][i] = 1;
}
void attach(int vr, int to, char c, int _len) {
  par[vr] = to, len[vr] = _len;
  go[to][c] = vr;
}
void extend(int i) {
  int leaf = SZ - 1;
  int v = leaf, vlen = ((int)(in).size()) - i;
  stack<int> path;
  while (!link[v].count(in[i])) path.push(v), vlen -= len[v], v = par[v];
  int w = link[v][in[i]];
  if (go[w].count(in[i + vlen])) {
    int u = go[w][in[i + vlen]];
    int& cp = pos[SZ];
    for (cp = pos[u] - len[u]; in[cp] == in[i + vlen]; cp += len[v])
      v = path.top(), path.pop(), vlen += len[v];
    attach(SZ, w, in[pos[u] - len[u]], len[u] - (pos[u] - pos[SZ]));
    attach(u, SZ, in[pos[SZ]], pos[u] - pos[SZ]);
    w = link[v][in[i]] = SZ++;
  }
  attach(SZ, w, in[i + vlen], in.size() - i - vlen);
  link[leaf][in[i]] = SZ;
  pos[SZ++] = in.size();
}
void build() {
  for (int i = ((int)(in).size()) - 1; i >= 0; --i) extend(i);
}
vector<string> nal;
vector<int> nal_id;
char buf[200010];
int id[MAXL];
int N, Q;
vector<int> lvs;
int lo[MAXV], hi[MAXV];
void dfs(int vr, int clen) {
  lo[vr] = ((int)(lvs).size());
  if (go[vr].empty()) {
    int beg = ((int)(in).size()) - clen;
    if (id[beg] >= 0) lvs.push_back(id[beg]);
  } else {
    for (auto& nxt : go[vr]) dfs(nxt.second, clen + len[nxt.second]);
  }
  hi[vr] = ((int)(lvs).size()) - 1;
}
vector<int> ans;
map<int, vector<pair<int, pair<int, int> > > > ask;
int sum[200010];
void add(int pos) {
  for (; pos < 200010; pos += pos & (-pos)) ++sum[pos];
}
int get(int l, int r) {
  int ret = 0;
  for (; r > 0; r -= r & (-r)) ret += sum[r];
  for (--l; l > 0; l -= l & (-l)) ret -= sum[l];
  return ret;
}
int main() {
  init();
  scanf("%d%d", &N, &Q);
  for (int i = 0; i < N; ++i) {
    scanf("%s", buf);
    nal.push_back(string(buf));
    in += nal.back();
    in.insert(in.end(), 1);
  }
  in.insert(in.end(), 0);
  for (int i = 0, cid = 1; i < ((int)(in).size()); ++i)
    if (in[i] < 2)
      id[i] = -1, cid++;
    else
      id[i] = cid;
  build();
  dfs(1, 0);
  for (int i = 0; i < ((int)(nal).size()); ++i) {
    int vr = 1, pos = 0;
    while (pos < ((int)(nal[i]).size()))
      vr = go[vr][nal[i][pos]], pos += len[vr];
    nal_id.push_back(vr);
  }
  ans.resize(Q + 1);
  for (int i = 1; i <= Q; ++i) {
    int l, r, k, vr;
    scanf("%d%d%d", &l, &r, &k);
    --k;
    vr = nal_id[k];
    ask[hi[vr]].push_back(make_pair(i, make_pair(l, r)));
    if (lo[vr]) ask[lo[vr] - 1].push_back(make_pair(-i, make_pair(l, r)));
  }
  int cp = 0;
  for (auto& i : ask) {
    int p = i.first;
    auto& q = i.second;
    while (cp <= p) add(lvs[cp]), ++cp;
    for (auto& cur : q) {
      int id = cur.first;
      int res = get(cur.second.first, cur.second.second);
      if (id < 0)
        ans[-id] -= res;
      else
        ans[id] += res;
    }
  }
  for (int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);
  return 0;
}