题目背景

CF1801G

题目描述

菲利普非常喜欢关于字符串的小题目。他已经解完了所有他知道的相关题目，但这还不能让他满足。于是，菲利普决定自己出一道题。

为此，他准备了一个字符串 $t$，以及一个由 $n$ 个字符串 $s_1, s_2, s_3, \ldots, s_n$ 组成的集合。菲利普还有 $m$ 个查询，每个查询中，他会取出字符串 $t$ 的第 $l_i$ 到第 $r_i$ 个字符组成的子串，并统计其中有多少个子串和集合中的某个字符串完全相同。更正式地说，菲利普想要计算有多少对位置 $(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$ 行，每行包含一个集合中的字符串 $s_i$，每个 $s_i$ 仅包含小写英文字母。记 $S$ 为所有 $s_i$ 的总长度。保证 $S \le 10^6$，且所有 $s_i$ 互不相同。

接下来的 $m$ 行，每行包含两个正整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le |t|$），表示第 $i$ 个查询中子串的左右端点。

输出格式

输出 $m$ 个整数，第 $i$ 个数表示第 $i$ 个查询的答案。

3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5

7 3 5 3 1

4 4
abcdca
ab
ca
bcd
openolympiad
1 5
2 2
2 6
1 6

2 0 2 3

提示

样例解释

在第一个样例中，第一个查询要求统计整个字符串中属于集合的子串个数。字符串 "aba" 对应的子串有 $[1, 3]$ 和 $[4, 6]$，字符串 "a" 对应的子串有 $[1, 1]$、$[3, 3]$、$[5, 5]$、$[7, 7]$，字符串 "ac" 对应的子串有 $[3, 4]$。所以总共有 $7$ 个子串与集合中的字符串匹配。

在第二个查询中，取 $t$ 的第 $1$ 到第 $3$ 个字符，即字符串 "aba"。其中 "aba" 匹配 $1$ 次，"a" 匹配 $2$ 次，"ac" 不出现。

在第三个查询中，取 $t$ 的第 $2$ 到第 $7$ 个字符，即字符串 "bacaba"。其中 "aba" 匹配 $1$ 次，"a" 匹配 $3$ 次，"ac" 匹配 $1$ 次。

评分说明

本题测试点分为 9 组。只有通过某一组的所有测试点，且通过部分之前组的所有测试点，才能获得该组分数。离线评测表示该组测试结果会在比赛结束后公布。

组别	分值	$n$	$m$	$\mid t\mid$	$S$	必须通过的组	备注
0		--					样例测试点
1	10	$n \le 100$	$m \le 100$	$\mid t\mid \le 100$	$S \le 10\,000$	0
2	12		$m \le 500$	$\mid t\mid \le 5000$	--	0, 1
3	7	$n \le 5000$	--	$\mid t\mid \le 5000$		0, 1, 2
4	8	$n \le 100$		$\mid t\mid \le 50\,000$
5	12	--		$\mid t \mid \le 100\,000$	$S \le 100\,000$	0, 1
6	8			$\mid t \mid \le 250\,000$		0, 1, 5
7	7			$\mid t \mid \le 500\,000$		0, 1, 5, 6
8				$\mid t \mid \le 750\,000$		0, 1, 5, 6, 7
9	29			--		0--8	离线评测