题目描述

本题字符串下标从 $1$ 开始。

定义两个字符串相加的结果为将这两个字符串首尾拼接形成的新字符串。

令 $f(a,b,c)=\sum\limits_{i=1}^{|a|}\sum\limits_{j=i}^{|a|}\sum\limits_{k=1}^{|b|}\sum\limits_{l=k}^{|b|}[a_{i,i+1,\cdots,j}+b_{k,k+1,\cdots,l} = c]$（$a,b,c$ 均为字符串）。

即有多少种方式从 $a,b$ 中分别选出一个非空子串使两个子串的和为 $c$。

给定 $n$ 个字符串 $s_1,s_2,s_3,\cdots,s_n$。

有 $q$ 次询问，每次询问给出三个正整数 $l,r,k$，求 $\sum\limits_{i=l}^r\sum\limits_{j=l}^rf(s_i,s_j,s_k)$。

输入格式

第一行包含两个整数 $n,q$。

下面 $n$ 行，每行一个只包含小写字母的非空字符串表示 $s_1,s_2,\cdots,s_n$。

下面 $q$ 行，每行三个正整数 $l,r,k$，表示一次询问。

输出格式

对于每个询问，每行输出一个整数表示答案。

3 3
a
aa
aaa
1 2 3
2 3 3
1 3 3

6
30
36

10 10
aabb
aba
abbba
abaccaab
abbba
ababababab
aaaaa
bbbbbb
aaba
abbba
1 10 10
1 4 5
3 6 4
2 8 1
1 5 4
2 10 7
2 9 2
4 5 5
5 5 6
8 9 10

241
31
51
105
40
136
460
17
0
0

5 5
a
ba
aba
ababa
abab
1 3 3
1 2 3
2 3 3
4 4 5
3 4 4

12
2
9
11
28

提示

样例解释

对于样例 $1$，给出部分 $f$ 函数的值。

• $f(s_1,s_1,s_3)=0$，$f(s_1,s_2,s_3)=1$，$f(s_1,s_3,s_3)=2$，$f(s_2,s_1,s_3)=1$，$f(s_2,s_2,s_3)=4$，$f(s_2,s_3,s_3)=7$，$f(s_3,s_1,s_3)=2$，$f(s_3,s_2,s_3)=7$，$f(s_3,s_3,s_3)=12$。

数据范围

本题采用捆绑测试。

令 $m=\sum|s_i|$。

$\text{Subtask}$	特殊性质	$\text{Score}$
$1$	$1\le n,m,q\le 3\times 10^3$	$17$
$2$	保证每次询问的 $k$ 各不相同	$23$
$3$	$1\le n,m,q\le 3\times 10^4$	$27$
$4$	字符串只包含小写字母 $\texttt{a}$	$19$
$5$	无特殊限制	$14$

对于 $100\%$ 的数据：$1\le n,m,q\le 10^5$，$1\le l \le r\le n$，$1\le k\le n$，字符串仅包含小写字母。