F. 疯狂的达芙

每个测试的时间限制：$4$ 秒
内存限制：$256$ MB

达芙对她的朋友们很生气。因此，她有时会无缘无故地让马利克从她的某个朋友那里拿走糖果！

题目描述

她有 $n$ 个朋友。第 $i$ 个朋友的名字是 $s_i$（名字不一定唯一）。达芙会提出 $q$ 次请求，让马利克从她的朋友那里拿走糖果。她虽然生气，但行为也有规则：

当她想要让马利克从她的某个朋友（比如第 $k$ 个朋友）那里拿走糖果时，她会选择两个数 $l$ 和 $r$，并告诉马利克从这位朋友那里恰好拿走

颗糖果。其中 $\operatorname{occur}(t, s)$ 表示字符串 $t$ 在字符串 $s$ 中出现的次数。

马利克无法计算出每次请求中需要拿走多少糖果，因此需要你的帮助。请告诉他每次请求的答案。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$）。

接下来的 $n$ 行，每行包含一个字符串 $s_i$，由小写英文字母组成，所有字符串的总长度 $\le 10^5$。

接下来的 $q$ 行，每行包含三个整数 $l$、$r$ 和 $k$（$1 \le l \le r \le n$，$1 \le k \le n$），表示一次请求：马利克需要从第 $k$ 个朋友那里拿走

颗糖果。

输出格式

对于每个请求，输出一行一个整数，表示对应的答案。

示例

输入

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