#x1054. CF587F Duff is Mad

    ID: 6075 远端评测题 4000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-AC 自动机fail 树统计根号分治子树转区间差分树状数组离线查询一维前缀和

CF587F Duff is Mad

题目描述

Duff 有 nn 位朋友,第 ii 位的名字为字符串 sis_i。不同的朋友可以同名。

对于两个字符串 t,st,s,记 occur⁡(t,s)\operatorname{occur}(t,s) 为 tt 在 ss 中作为连续子串的出现次数。每个符合条件的起始位置计一次,出现位置可以重叠。

有 qq 次询问。每次给出 l,r,kl,r,k,求区间 [l,r][l,r] 内每位朋友的名字在 sks_k 中出现的次数之和,即

∑i=lroccur⁡(si,sk).\sum_{i=l}^{r}\operatorname{occur}(s_i,s_k).

输入格式

第一行两个整数 n,qn,q(1≤n,q≤1051\le n,q\le10^5)。

接下来 nn 行,第 ii 行给出由小写英文字母组成的非空字符串 sis_i,满足 ∑i=1n∣si∣≤105\sum_{i=1}^n |s_i|\le10^5。

接下来 qq 行,每行三个整数 l,r,kl,r,k,满足 1≤l≤r≤n1\le l\le r\le n、1≤k≤n1\le k\le n。

输出格式

按询问顺序,每行输出一个整数。

样例

5 5
a
ab
abab
ababab
b
1 5 4
3 5 4
1 5 2
1 5 3
1 4 1
12
6
3
7
1

Codeforces 原题 CF587F