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;
int n, m, total_len[400010];
int pos[400010];
namespace Segment_Tree {
struct node {
  node *l, *r;
  int sum;
  void *operator new(size_t, node *ls, node *rs, int sum) {
    node *cnt = new node[1];
    cnt->l = ls;
    cnt->r = rs;
    cnt->sum = sum;
    return cnt;
  }
} * tree[400010];
node *insert(node *p, int l, int r, int pos) {
  if (l == r) return new (0x0, 0x0, p->sum + 1) node;
  int mid = l + r >> 1;
  if (pos <= mid)
    return new (insert(p->l, l, mid, pos), p->r, p->sum + 1) node;
  else
    return new (p->l, insert(p->r, mid + 1, r, pos), p->sum + 1) node;
}
int query(node *p1, node *p2, int l, int r, int x, int y) {
  if (x <= l && r <= y) return p1->sum - p2->sum;
  int mid = l + r >> 1;
  if (y <= mid)
    return query(p1->l, p2->l, l, mid, x, y);
  else if (x > mid)
    return query(p1->r, p2->r, mid + 1, r, x, y);
  else {
    return query(p1->l, p2->l, l, mid, x, y) +
           query(p1->r, p2->r, mid + 1, r, x, y);
  }
}
};  // namespace Segment_Tree
struct Suffix_Tree {
  int head[400010], next[400010], edge[400010], tot;
  void add(int a, int b) {
    ++tot;
    next[tot] = head[a];
    head[a] = tot;
    edge[tot] = b;
  }
  int _index, in[400010], out[400010], seq[400010];
  void dfs(int u) {
    in[u] = ++_index;
    seq[_index] = u;
    for (int i = head[u]; i; i = next[i]) {
      dfs(edge[i]);
    }
    out[u] = _index;
  }
  void update();
  int query(int x, int l, int r) {
    return Segment_Tree::query(Segment_Tree::tree[out[x]],
                               Segment_Tree::tree[in[x] - 1], 1, total_len[n],
                               l, r);
  }
} tr;
struct Suffix_Automation {
  struct node {
    int len, pre, son[26];
    vector<int> right;
    node() { right.clear(); }
  } a[400010];
  int tail, tot;
  void insert(int k, int id) {
    int q, p, nq, np;
    if (a[tail].son[k]) {
      if (a[q = a[tail].son[k]].len == a[tail].len + 1) {
        tail = q;
        a[q].right.push_back(id);
      } else {
        nq = ++tot;
        memcpy(a[nq].son, a[q].son, sizeof(a[q].son));
        a[nq].right.push_back(id);
        a[nq].pre = a[q].pre;
        a[nq].len = a[tail].len + 1;
        a[q].pre = nq;
        for (p = tail; a[p].son[k] == q; p = a[p].pre) a[p].son[k] = nq;
        tail = nq;
      }
    } else {
      a[np = ++tot].len = a[tail].len + 1;
      a[np].right.push_back(id);
      for (p = tail; p && !a[p].son[k]; p = a[p].pre) a[p].son[k] = np;
      if (!a[p].son[k]) {
        a[p].son[k] = np;
        a[np].pre = p;
      } else {
        if (a[q = a[p].son[k]].len == a[p].len + 1) {
          a[np].pre = q;
        } else {
          nq = ++tot;
          memcpy(a[nq].son, a[q].son, sizeof(a[q].son));
          a[nq].pre = a[q].pre;
          a[nq].len = a[p].len + 1;
          a[np].pre = a[q].pre = nq;
          for (; a[p].son[k] == q; p = a[p].pre) a[p].son[k] = nq;
        }
      }
      tail = np;
    }
  }
  void draw() {
    for (int i = 1; i <= tot; i++) {
      tr.add(a[i].pre, i);
    }
  }
} sam;
void Suffix_Tree::update() {
  Segment_Tree::tree[0] = new (0x0, 0x0, 0) Segment_Tree::node;
  Segment_Tree::tree[0]->l = Segment_Tree::tree[0]->r = Segment_Tree::tree[0];
  for (int i = 1; i <= _index; i++) {
    int x = seq[i];
    Segment_Tree::tree[i] = Segment_Tree::tree[i - 1];
    for (int j = 0; j < sam.a[x].right.size(); j++) {
      Segment_Tree::tree[i] = Segment_Tree::insert(
          Segment_Tree::tree[i], 1, total_len[n], sam.a[x].right[j]);
    }
  }
}
char str[400010];
int main() {
  int a, b, c;
  total_len[0] = 1;
  scanf("%d%d\n", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%s", str);
    sam.tail = 0;
    for (int j = 0; str[j]; j++) {
      sam.insert(str[j] - 'a', total_len[i - 1] + j);
    }
    total_len[i] = total_len[i - 1] + strlen(str);
    pos[i] = sam.tail;
  }
  sam.draw();
  tr.dfs(0);
  tr.update();
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &a, &b, &c);
    printf("%d\n", tr.query(pos[c], total_len[a - 1], total_len[b] - 1));
  }
  return 0;
}