为此,他采用了字符串 $$$t$$$ 和一组 $$$n$$$ 字符串 $$$s_1$$$、$$$s_2$$$、$$$s_3$$$、...、$$$s_n$$$。 Philip 有 $$$m$$$ 个查询,在第 $$$i$$$ 个查询中,Philip 希望获取字符串 $$$t$$$ 中从第 $$$l_i$$$ 到第 $$$r_i$$$ 个字符的子字符串,并计算与集合中某个字符串匹配的子字符串的数量。更正式地说,Philip 想要计算位置对 $$$a$$$、$$$b$$$ 的数量,使得 $$$l_i \le a \le b \le r_i$$$,并且字符串 $$$t$$$ 从第 $$$a$$$ 到第 $$$b$$$ 字符的子字符串与集合中的某个字符串 $$$s_j$$$ 一致。
字符串$$$t$$$从第$$$a$$$到第$$$b$$$字符的子字符串是从$$$t$$$中删除开头的$$$a - 1$$$字符和$$$|t|得到的字符串。 - 从末尾开始 b$$$ 个字符,其中 $$$|t|$$$ 表示字符串 $$$t$$$ 的长度。
菲利普已经解决了这个问题,但是你能吗?
输入
第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500\,000$$$) - 集合中的行数和查询数。
第二行包含单个字符串 $$$t$$$,由英文字母的小写字母组成 ($$$1 \le |t| \le 5 \cdot 10^6$$$)。
以下 $$$n$$$ 行描述了该集合中的字符串。在其中的第 $$$i$$$ 中,给出单个字符串 $$$s_i$$$,由英文字母的小写字母组成。用 $$$S$$$ 表示集合中所有字符串的总长度。保证$$$S \le 10^6$$$,并且$$$s_i$$$的所有字符串都不同。
在以下行中,输入查询。其中第 $$$i$$$ 包含两个正整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le |t|$$$) - 来自第 $$$i$$$ 查询的子字符串 $$$t$$$ 的左边界和右边界。
输出
在一行中,打印 $$$m$$$ 个整数,其中第 $$$i$$$ 个整数应等于第 $$$i$$$ 个查询的答案。
示例
输入 #1
3 5 abacaba aba a ac 1 7 1 3 2 7 2 5 4 5
输出 #1
7 3 5 3 1
输入 #2
4 4 abcdca ab ca bcd openolympiad 1 5 2 2 2 6 1 6
输出 #2
2 0 2 3
注意
在第一个示例中,第一个查询需要整个字符串来计算集合中包含的子字符串的数量。子字符串 $$$[1, 3]$$$ 和 $$$[4, 6]$$$ 与字符串“aba”一致。子字符串与字符串“a”$$$[1, 1]$$$、$$$[3, 3]$$$、$$$[5, 5]$$$、$$$[7, 7]$$$ 匹配。子字符串 $$$[3, 4]$$$ 与字符串“ac”匹配。总共,字符串“abacaba”的 7 个子字符串与集合中的字符串匹配。
在第二个查询中,从源字符串中取出位置1到位置3的子字符串,即字符串“aba”。字符串“aba”进入其中 1 次,字符串“a”进入其中 2 次,字符串“ac”作为子字符串不进入其中一次。 在第三个查询中,从源字符串中取出第2个到第7个位置的子字符串,这就是字符串“bacaba”。作为子串,字符串“aba”被包含在其中1次,字符串“a”被包含3次,字符串“ac”被包含1次。