CF1801G A task for substrings

可以在 [P13531](https://www.luogu.com.cn/problem/P13531) 评测本题。

菲利普非常喜欢关于字符串的小题目。他已经解完了所有他知道的相关题目，但这还不能让他满足。于是，菲利普决定自己出一道题。 为此，他准备了一个字符串 $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$ 个查询的答案。

### 样例解释 在第一个样例中，第一个查询要求统计整个字符串中属于集合的子串个数。字符串 "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$ 次。