P10176 「OICon-02」Native Faith

本题字符串下标从 $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)$。

无

无

### 样例解释 对于样例 $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$，字符串仅包含小写字母。