← 返回题目列表

Codeforces · 547/E

E. 迈克和朋友们

中文机器翻译题面 查看原题

祖国真是个奇怪的国家啊!所有电话号码都是由小写英文字母组成的字符串。一个电话号码可以与几只熊相关联,这真是太奇怪了!

在那个国家有一个摇滚乐队叫CF,由n只熊(包括迈克)组成,编号从1到n。

CF第i个成员的电话号码是si。 5月17日是一个名为“电话日”的假期。在最后的电话通话日中,每个人都拨打了属于其号码子串的所有号码(一个人可能会多次拨打某个号码)。特别是,每个人都称呼自己(那是一个非常奇怪的国家)。

将 CF 的第 i 个成员呼叫 CF 的第 j 个成员的次数表示为 call(i, j)。

极客迈克有 q 个问题想问你。在每个问题中,他都会给你数字 l、r 和 k,你应该告诉他数字

$$\sum_{i=l}^{r} 调用(i,k)$$

输入

输入的第一行包含整数 n 和 q(1 ≤ n ≤ 2 × 105 且 1 ≤ q ≤ 5 × 105)。

接下来的 n 行包含电话号码,第 i 行包含由小写英文字母组成的字符串 si ($$1 \leq \sum_{i=1}^{n} |s_i| \leq 2 \times 10^5$$)。

接下来的 q 行包含有关问题的信息,每行包含整数 l、r 和 k(1 ≤ l ≤ r ≤ n 和 1 ≤ k ≤ n)。

输出

在单独的行中打印每个问题的答案。

示例

输入 #1

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

输出 #1

7
5
6
3
6