bobo 有 $n$ 个字符串 $S_1, S_2, \dots, S_n$。有一天，他的朋友 yiyi 来问他 $q$ 个问题：在字符串 $S_{l_i}, S_{l_i+1}, \dots, S_{r_i}$ 中，有多少个字符串包含 $P_i$ 作为其子串？

请帮助 bobo 找到答案。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n, q \le 200000$)。

接下来 $n$ 行，每行包含一个字符串 $S_i$ ($|S_1| + |S_2| + \dots + |S_n| \le 200000$)。

最后 $q$ 行，每行包含两个整数 $l_i, r_i$ 和一个字符串 $P_i$。 ($1 \le l_i \le r_i \le n, |P_1| + |P_2| + \dots + |P_q| \le 200000$)

所有字符串均由字符 “a” 和 “b” 组成。

输出格式

对于每个问题，输出一个整数表示答案。

样例

输入格式 1

4 2
a
b
ab
bab
1 3 a
1 4 ab

输出格式 1

2
2