题目描述
Duff 有 n 位朋友,第 i 位的名字为字符串 si。不同的朋友可以同名。
对于两个字符串 t,s,记 occur(t,s) 为 t 在 s 中作为连续子串的出现次数。每个符合条件的起始位置计一次,出现位置可以重叠。
有 q 次询问。每次给出 l,r,k,求区间 [l,r] 内每位朋友的名字在 sk 中出现的次数之和,即
i=l∑roccur(si,sk).
输入格式
第一行两个整数 n,q(1≤n,q≤105)。
接下来 n 行,第 i 行给出由小写英文字母组成的非空字符串 si,满足 ∑i=1n∣si∣≤105。
接下来 q 行,每行三个整数 l,r,k,满足 1≤l≤r≤n、1≤k≤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