祖国真是个奇怪的国家啊!所有电话号码都是由小写英文字母组成的字符串。一个电话号码可以与几只熊相关联,这真是太奇怪了!
在那个国家有一个摇滚乐队叫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