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*. 

Phone number of *i*-th member of CF is *s*<sub class="lower-index">*i*</sub>. 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
The first line of input contains integers *n* and *q* (1 ≤ *n* ≤ 2 × 10<sup class="upper-index">5</sup> and 1 ≤ *q* ≤ 5 × 10<sup class="upper-index">5</sup>).

The next *n* lines contain the phone numbers, *i*-th line contains a string *s*<sub class="lower-index">*i*</sub> consisting of lowercase English letters (<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b60bbd11dae7b5f43c55918a57e5e68833b6b60a.png" style="max-width: 100.0%;max-height: 100.0%;"/>).

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*).
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, q;
char str[200005];
vector<int> fail[200005];
struct qqq
{
    int k, i, f;
};
vector<qqq> quer[200005];

struct ac
{
    struct tr
    {
        int son[26], fail, fa;
        int &operator[](const int x)
        {
            return son[x];
        }
    } tr[200005];
    int is_string[2000005];
    int cnt = 0;
    void insert(char *str, int x)
    {
        int len = strlen(str);
        int now = 0;
        for (int i = 0; i < len; i++)
        {
            int nxt = str[i] - 'a';
            if (!tr[now][nxt])
            {
                tr[now][nxt] = ++cnt;
                tr[cnt].fa = now;
            }
            now = tr[now][nxt];
        }
        is_string[x] = now;
    }
    void build()
    {
        queue<int> q;
        for (int i = 0; i < 26; i++)
        {
            if (tr[0][i])
                q.push(tr[0][i]);
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (tr[u][i])
                {
                    tr[tr[u][i]].fail = tr[tr[u].fail][i];
                    q.push(tr[u][i]);
                }
                else
                    tr[u][i] = tr[tr[u].fail][i];
            }
        }
        for (int i = 1; i <= cnt; i++)
        {
            fail[tr[i].fail].push_back(i);
        }
    }
} zdj;

int lb[200005], rb[200005], cnt = 0;
void dfs(int x)
{
    lb[x] = ++cnt;
    int len = fail[x].size();
    for (int i = 0; i < len; i++)
        dfs(fail[x][i]);
    rb[x] = cnt;
}

struct BIT
{
    int bit[200005] = {0};
    int lowbit(int x)
    {
        return x & (-x);
    }
    void modify(int p, int v)
    {
        for (; p <= cnt; p += lowbit(p))
            bit[p] += v;
    }
    int query(int p)
    {
        int ans = 0;
        for (; p > 0; p -= lowbit(p))
            ans += bit[p];
        return ans;
    }
} bit;
void pushup(int i)
{
    int now = zdj.is_string[i];
    while (now)
    {
        //printf("%d\n", lb[now]);
        bit.modify(lb[now], 1);
        now = zdj.tr[now].fa;
        // for (int i = 1; i <= cnt; i++)
        // {
        //     printf("%d%c", bit.bit[i], " \n"[i == cnt]);
        // }
    }
}
int ask(int i)
{
    int k = zdj.is_string[i];
    return bit.query(rb[k]) - bit.query(lb[k] - 1);
}
int ans[500005];
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", str);
        zdj.insert(str, i);
    }
    zdj.build();
    // for (int i = 0; i <= zdj.cnt; i++)
    // {
    //     printf("%d:", i);
    //     for (int j = 0; j < (int)fail[i].size(); j++)
    //     {
    //         printf("%d ", fail[i][j]);
    //     }
    //     putchar('\n');
    // }
    dfs(0);
    // for (int i = 1; i <= n; i++)
    // {
    //     printf("%d%c", zdj.is_string[i], " \n"[i == n]);
    // }
    // for (int i = 0; i <= cnt; i++)
    // {
    //     printf("%d%c", lb[i], " \n"[i == cnt]);
    // }
    // for (int i = 0; i <= cnt; i++)
    // {
    //     printf("%d%c", rb[i], " \n"[i == cnt]);
    // }
    for (int i = 1; i <= q; i++)
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        quer[r].push_back((qqq){k, i, 1});
        quer[l - 1].push_back((qqq){k, i, -1});
    }
    for (int i = 1; i <= n; i++)
    {
        pushup(i);
        int len1 = quer[i].size();
        for (int j = 0; j < len1; j++)
        {
            ans[quer[i][j].i] += quer[i][j].f * ask(quer[i][j].k);
        }
    }
    // for (int i = 1; i <= cnt; i++)
    // {
    //     printf("%d%c", bit.bit[i], " \n"[i == cnt]);
    // }
    for (int i = 1; i <= q; i++)
    {
        printf("%d\n", ans[i]);
    }
    // system("pause");
    return 0;
}

/*
20 11
e
n
i
g
g
b
u
v
g
t
f
k
n
o
l
h
w
h
o
e
6 13 5
20 20 13
1 9 4
1 7 13
18 18 12
19 19 18
8 20 20
13 15 11
15 19 9
2 19 5
15 18 5
*/
	  			       			 	 		  		  	  	