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 MX = (1 << 20);
class BIT {
  int MX, *bit;

 public:
  BIT() {
    MX = 0;
    bit = NULL;
  };
  void init(int N) {
    MX = N;
    bit = new int[MX + 1];
    for (int j = 0; j <= MX; j++) bit[j] = 0;
  }
  int get(int x) {
    int ret = 0;
    while (x > 0) {
      ret += bit[x];
      x -= x & (-x);
    }
    return ret;
  }
  void add(int x, int V) {
    while (x <= MX) {
      bit[x] += V;
      x += x & (-x);
    }
  }
} tree;
class Suffix_Array {
  string str;

 public:
  int cnt[MX], n;
  void init(string ss) {
    str = " " + ss;
    n = str.size();
  }
  int x[MX], y[MX], sa[MX];
  void count_sort(int lim) {
    for (int j = 0; j <= lim; j++) cnt[j] = 0;
    for (int j = 0; j < n; j++) ++cnt[x[y[j]]];
    for (int j = 1; j <= lim; j++) cnt[j] += cnt[j - 1];
    for (int j = n - 1; j >= 0; j--) sa[--cnt[x[y[j]]]] = y[j];
  }
  void sparse() {
    for (int j = 0; j < n; j++) x[j] = str[j] + 1, y[j] = j;
    int lim = max(n, 300);
    count_sort(lim);
    for (int po = 1; po < n; po <<= 1) {
      int L = 0;
      for (int j = n - po; j < n; j++) y[L++] = j;
      for (int j = 0; j < n; j++)
        if (sa[j] >= po) y[L++] = sa[j] - po;
      count_sort(lim);
      swap(x, y);
      x[sa[0]] = 0;
      L = 1;
      for (int j = 1; j < n; j++) {
        if (y[sa[j - 1]] != y[sa[j]])
          x[sa[j]] = L++;
        else if (y[sa[j - 1] + po] != y[sa[j] + po])
          x[sa[j]] = L++;
        else
          x[sa[j]] = L - 1;
      }
      lim = L;
    }
  }
  int lcp[MX], phi[MX];
  void suffix_array(vector<int> &SA, vector<int> &ret_lcp) {
    SA.clear();
    ret_lcp.clear();
    ret_lcp.resize(n - 1);
    sparse();
    for (int j = 1; j < n; j++) SA.push_back(sa[j] - 1);
    str = str.substr(1, n - 1);
    --n;
    int sz_ = str.size();
    phi[SA[0]] = -1;
    for (int j = 1; j < sz_; j++) phi[SA[j]] = SA[j - 1];
    for (int i = 0, L = 0; i < sz_; i++) {
      if (phi[i] == -1) {
        lcp[i] = 0;
        continue;
      }
      while (str[i + L] == str[phi[i] + L]) ++L;
      lcp[i] = L;
      L = max(L - 1, 0);
    }
    for (int j = 0; j < sz_; j++) ret_lcp[j] = lcp[SA[j]];
  }
} Suff;
int par[MX], L[MX], R[MX];
void init(int all) {
  for (int j = 0; j < all; j++) L[j] = par[j] = R[j] = j;
}
int find_(int x) {
  if (x == par[x]) return x;
  return par[x] = find_(par[x]);
}
void merge_(int x, int y) {
  x = find_(x), y = find_(y);
  par[y] = x;
  L[x] = min(L[x], L[y]);
  R[x] = max(R[x], R[y]);
}
vector<int> where[MX];
int all;
vector<int> SA, lcp;
void relax(int L) {
  for (auto pp : where[L]) {
    if (pp) merge_(pp, pp - 1);
    if (pp + 1 < all && lcp[pp + 1] >= L) merge_(pp, pp + 1);
  }
}
int n, QN, which[MX], idx[MX];
string pat;
char ccc[MX];
vector<pair<int, pair<int, int> > > Queries[MX];
int ss[MX], ee[MX], psize[MX], xoxo[MX], ans[MX];
int main() {
  string str;
  scanf("%d %d", &n, &QN);
  tree.init(n + 10);
  for (int j = 1; j <= n; j++) {
    scanf("%s", ccc);
    int pp = str.size();
    pat = ccc;
    which[j] = pp;
    psize[j] = pat.size();
    str += pat + "$";
    for (int i = pp; i + 1 < str.size(); i++) idx[i] = j;
  }
  Suff.init(str);
  Suff.suffix_array(SA, lcp);
  all = SA.size();
  for (int j = 0; j < all; j++) xoxo[j] = idx[SA[j]];
  swap(xoxo, idx);
  memset(xoxo, 0, sizeof(xoxo));
  for (int j = 0; j < all; j++) {
    if (which[idx[j]] == SA[j]) xoxo[idx[j]] = j;
  }
  swap(xoxo, which);
  for (int j = 0; j < all; j++) where[lcp[j]].push_back(j);
  int cur = all;
  vector<pair<int, pair<int, int> > > sorted;
  for (int j = 1; j <= QN; j++) {
    scanf("%d %d", &ss[j], &ee[j]);
    int K;
    scanf("%d", &K);
    sorted.push_back({psize[K], {K, j}});
  }
  init(all);
  sort(sorted.rbegin(), sorted.rend());
  for (auto Q : sorted) {
    while (cur >= Q.first) {
      relax(cur);
      --cur;
    }
    int pt = Q.second.first, idx = Q.second.second;
    int bakr = find_(which[pt]);
    int st = L[bakr], en = R[bakr];
    Queries[en].push_back({idx, {ss[idx], ee[idx]}});
    if (st > 0) Queries[st - 1].push_back({idx, {-ss[idx], -ee[idx]}});
  }
  for (int j = 0; j < all; j++) {
    if (idx[j]) tree.add(idx[j], 1);
    for (auto Q : Queries[j]) {
      int idx = Q.first, st = Q.second.first, en = Q.second.second;
      int coef = 1;
      if (st < 0) coef = -1;
      st = abs(st), en = abs(en);
      ans[idx] += coef * (tree.get(en) - tree.get(st - 1));
    }
  }
  for (int j = 1; j <= QN; j++) printf("%d\n", ans[j]);
}