P10176 "OICon-02" Native Faith

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

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.

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

### 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