CF587F Duff is Mad

Duff 对她的朋友们很生气。这就是为什么她有时会无缘无故地让 Malek 从她的一个朋友那里拿走糖果！  她有 $n$ 个朋友。她的第 $i$ 个朋友的名字是 $s_{i}$（他们的名字不一定唯一）。$q$ 次，她让 Malek 从她的朋友们那里拿走糖果。她很愤怒，但她的行为也有规则。当她想让 Malek 从她的一个朋友（比如第 $k$ 个朋友）那里拿走糖果时，她会选择两个数字 $l$ 和 $r$，然后告诉 Malek 从他/她那里拿走恰好 $\sum_{i=l}^{r} occur(s_i, s_k)$ 颗糖果，其中 $occur(t,s)$ 是字符串 $t$ 在 $s$ 中出现的次数。 Malek 无法计算每次 Duff 的请求中需要拿走多少糖果。这就是为什么她向你求助。请告诉他每次请求需要拿走多少糖果。

第一行输入包含两个整数 $n$ 和 $q$（$1 \leq n,q \leq 10^{5}$）。 接下来 $n$ 行包含名字。其中第 $i$ 行包含一个由小写英文字母组成的字符串 $s_{i}$（$|s_i| \geq 1$，$\sum \limits_{1\le i \le n} |s_i| \le 10^5$）。 接下来 $q$ 行包含请求。每行包含三个整数 $l$、$r$ 和 $k$（表示 Malek 应该从 Duff 的第 $k$ 个朋友那里拿走 $\sum_{i=l}^{r} occur(s_i, s_k)$ 颗糖果）。

对于每个请求，在一行中输出答案。

由 ChatGPT 5 翻译