Mike and Friends

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有 $n$ 个编号为 $1$ 到 $n$ 的字符串 $s_i$。定义 $call(i,j)$ 为字符串 $s_j$ 在字符串 $s_i$ 中作为连续子串出现的次数；允许不同出现位置重叠。

现有 $q$ 个询问。每个询问给出 $l,r,k$，请计算

所有字符串仅包含小写英文字母。

输入格式

第一行输入两个整数 $n,q$。

接下来 $n$ 行，第 $i$ 行输入字符串 $s_i$。

接下来 $q$ 行，每行输入三个整数 $l,r,k$，表示一个询问。

输出格式

对每个询问输出一行一个整数。

样例输入 1

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

样例输出 1

7
5
6
3
6

数据范围

对于所有数据，$1\le n\le2\times10^5$，$1\le q\le5\times10^5$，$1\le\sum |s_i|\le2\times10^5$，$1\le l\le r\le n$，$1\le k\le n$。