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 inf = 1e9;
const long long INF = 1e18;
const double eps = 1e-10;
mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T>
inline void upmin(T &x, T y) {
  x = x > y ? y : x;
}
template <class T>
inline void upmax(T &x, T y) {
  x = x < y ? y : x;
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class A, class B, class C>
string to_string(tuple<A, B, C> p);
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <class A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A, class B, class C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <class A, class B, class C, class D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug() { cerr << endl; }
template <class T, class... U>
void debug(const T &h, const U &...t) {
  cerr << to_string(h) << ' ';
  debug(t...);
}
const int maxnode = 4e5 + 100;
const int sigma_size = 26;
int n, q;
char str[maxnode];
char s[maxnode];
const int maxn = 3e6 + 233;
struct node {
  int op, x, y, c, id;
  bool operator<(const node &r) const {
    return x < r.x || (x == r.x && y < r.y);
  }
} a[maxn], tmp[maxn];
struct AC {
  int ch[maxnode][sigma_size];
  int val[maxnode];
  int f[maxnode];
  int last[maxnode];
  int pos[maxnode];
  int in[maxnode];
  int out[maxnode];
  int dfs_clock;
  int rk[maxnode];
  vector<int> p[maxnode];
  vector<int> G[maxnode];
  int sz;
  void init() {
    sz = 1;
    memset(ch[0], 0, sizeof(ch[0]));
  }
  int idx(char c) { return c - 'a'; }
  void insert(char *s, int v = 1) {
    int n = strlen(s);
    int u = 0;
    for (int i = 0; i < n; i++) {
      int c = idx(s[i]);
      if (!ch[u][c]) {
        ch[u][c] = sz;
        memset(ch[sz], 0, sizeof(ch[sz]));
        val[sz++] = 0;
      }
      u = ch[u][c];
      p[v].emplace_back(u);
    }
    val[u] = v;
    pos[v] = u;
  }
  void getfail() {
    queue<int> q;
    f[0] = 0;
    for (int i = 0; i < sigma_size; i++) {
      int u = ch[0][i];
      if (u) {
        f[u] = last[u] = 0;
        q.push(u);
      }
    }
    while (!q.empty()) {
      int r = q.front();
      q.pop();
      for (int c = 0; c < sigma_size; c++) {
        int u = ch[r][c];
        if (!u) {
          ch[r][c] = ch[f[r]][c];
          continue;
        }
        q.push(u);
        int v = f[r];
        while (v && !ch[v][c]) v = f[v];
        f[u] = ch[v][c];
        last[u] = val[f[u]] ? f[u] : last[f[u]];
      }
    }
  }
  void print(int i) {
    if (i) {
      printf("%d\n", i);
      print(last[i]);
    }
  }
  void find(char *s) {
    int n = strlen(s);
    int j = 0;
    for (int i = 0; i < n; i++) {
      int c = idx(s[i]);
      j = ch[j][c];
      if (val[j])
        print(j);
      else if (last[j])
        print(last[j]);
    }
  }
  void build() {
    for (int i = 1; i < sz; i++) {
      G[f[i]].emplace_back(i);
    }
    dfs(0);
  }
  void dfs(int u) {
    in[u] = ++dfs_clock;
    rk[dfs_clock] = u;
    for (auto v : G[u]) {
      dfs(v);
    }
    out[u] = dfs_clock;
  }
} ac;
long long res[maxn];
long long c[maxn];
void add(int x, int d) {
  while (x < maxn) {
    c[x] += d;
    x += (x & -x);
  }
}
long long query(int x) {
  long long ret = 0;
  while (x) {
    ret += c[x];
    x -= (x & -x);
  }
  return ret;
}
void cdq(int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  cdq(l, mid);
  cdq(mid + 1, r);
  int pl = l, tot = l, pr = mid + 1;
  while (pl <= mid && pr <= r) {
    if (a[pl].x <= a[pr].x) {
      if (!a[pl].op) add(a[pl].y, a[pl].c);
      tmp[tot++] = a[pl++];
    } else {
      if (a[pr].op) res[a[pr].id] += a[pr].c * query(a[pr].y);
      tmp[tot++] = a[pr++];
    }
  }
  while (pl <= mid) {
    if (!a[pl].op) add(a[pl].y, a[pl].c);
    tmp[tot++] = a[pl++];
  }
  while (pr <= r) {
    if (a[pr].op) res[a[pr].id] += a[pr].c * query(a[pr].y);
    tmp[tot++] = a[pr++];
  }
  for (int i = l; i <= mid; i++)
    if (!a[i].op) add(a[i].y, -a[i].c);
  for (int i = l; i <= r; i++) a[i] = tmp[i];
}
int main() {
  scanf("%d %d", &n, &q);
  ac.init();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    ac.insert(s, i);
  }
  ac.getfail();
  ac.build();
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    for (auto j : ac.p[i]) {
      a[++tot] = node{0, ac.in[j], i, 1, 0};
    }
  }
  for (int i = 1; i <= q; i++) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    int p = ac.pos[k];
    a[++tot] = node{1, ac.in[p] - 1, l - 1, 1, i};
    a[++tot] = node{1, ac.in[p] - 1, r, -1, i};
    a[++tot] = node{1, ac.out[p], l - 1, -1, i};
    a[++tot] = node{1, ac.out[p], r, 1, i};
  }
  cdq(1, tot);
  for (int i = 1; i <= q; i++) {
    printf("%lld\n", res[i]);
  }
  return 0;
}