Problem Description

In this problem, string indices start from $1$.

Define the result of adding two strings as the new string formed by concatenating the two strings end to end.

Let $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$ are all strings).

That is, how many ways are there to choose a non-empty substring from each of $a$ and $b$ such that the sum (concatenation) of the two substrings equals $c$.

Given $n$ strings $s_1,s_2,s_3,\cdots,s_n$.

There are $q$ queries. Each query gives three positive integers $l,r,k$. Compute $\sum\limits_{i=l}^r\sum\limits_{j=l}^rf(s_i,s_j,s_k)$.

Input Format

The first line contains two integers $n,q$.

The next $n$ lines each contain a non-empty string consisting only of lowercase letters, representing $s_1,s_2,\cdots,s_n$.

The next $q$ lines each contain three positive integers $l,r,k$, representing one query.

Output Format

For each query, output one integer per line representing the answer.

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

Hint

Sample Explanation

For sample $1$, some values of the function $f$ are given.

• $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$.

Constraints

This problem uses bundled testdata.

Let $m=\sum|s_i|$.

::cute-table | $\text{Subtask}$ | Special Property | $\text{Score}$ | | :-----------: | :-----------: | :-----------: | | $1$ | $n,m,q\le 3\times 10^3$ | $17$ | | $2$ | The $k$ in each query are all different | $23$ | | $3$ | $n,m,q\le 3\times 10^4$ | $27$ | | $4$ | The strings only contain the lowercase letter $\texttt{a}$ | $19$ | | $5$ | None | $14$ |

For $100\%$ of the data: $1\le n,m,q\le 10^5$, $1\le l \le r\le n$, $1\le k\le n$, and the strings contain only lowercase letters.

Translated by ChatGPT 5