达芙对她的朋友很生气。这就是为什么她有时会让马利克无缘无故地从她的一位朋友那里拿走糖果!
她有 n 个朋友。她的第 i 个朋友的名字是 si(他们的名字不一定是唯一的)。 q 次,她要求马利克从她的朋友那里拿走糖果。她很生气,但她也遵守规则。当她想要要求 Malek 从她的一个朋友(例如 k)那里拿走糖果时,她选择两个数字 l 和 r 并告诉 Malek 从他/她那里拿走 $$\sum_{i=l}^{r}occurred(s_i, s_k)$$ 糖果,其中occurrence(t, s) 是字符串 t 在 s 中出现的次数。
Malek 无法计算出 Duff 的每次请求需要多少糖果。这就是为什么她请求你的帮助。请告诉他每次请求要带多少糖果。
输入
输入的第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 105)。
接下来的 n 行包含名称。其中第 i 个包含字符串 si,由小写英文字母组成 ($$1 \leq \sum_{i=1}^{n} |s_i| \leq 10^5$$)。
接下来的 q 行包含请求。它们每个都包含三个整数,l、r 和 k(表示 Malek 应该从 Duff 的第 k 个朋友那里拿走 $$\sum_{i=l}^{r}occurred(s_i, s_k)$$ 糖果)。
输出
在一行中打印每个请求的答案。
示例
输入 #1
5 5 a ab abab ababab b 1 5 4 3 5 4 1 5 2 1 5 3 1 4 1
输出 #1
12 6 3 7 1