CF1801G.A task for substrings

Philip is very fond of tasks on the lines. He had already solved all the problems known to him, but this was not enough for him. Therefore, Philip decided to come up with his own task.

To do this, he took the string $t$ and a set of $n$ strings $s_1$, $s_2$, $s_3$, ..., $s_n$. Philip has $m$ queries, in the $i$th of them, Philip wants to take a substring of the string $t$ from $l_i$th to $r_i$th character, and count the number of its substrings that match some string from the set. More formally, Philip wants to count the number of pairs of positions $a$, $b$, such that $l_i \le a \le b \le r_i$, and the substring of the string $t$ from $a$th to $b$th character coincides with some string $s_j$ from the set.

A substring of the string $t$ from $a$th to $b$th character is a string obtained from $t$ by removing the $a - 1$ character from the beginning and $|t| - b$ characters from the end, where $|t|$ denotes the length of the string $t$.

Philip has already solved this problem, but can you?

菲利普非常喜欢与字符串子串相关的问题。他早已解决了所有已知的此类题目，但这仍不能满足他。因此，菲利普决定自己构造一道新题。

为此，他取了一个字符串 $t$ 和一个包含 $n$ 个字符串的集合 $s_1$, $s_2$, $s_3$, ..., $s_n$。菲利普共有 $m$ 个查询；在第 $i$ 个查询中，他希望取出字符串 $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$ 的长度。

菲利普已经解决了这个问题，但你能吗？

The first line contains two positive integers $n$ and $m$ ($1 \le n, m \le 500\,000$) — the number of rows in the set and the number of queries.

The second line contains a single string $t$ consisting of lowercase letters of the English alphabet ($1 \le |t| \le 5 \cdot 10^6$).

The following $n$ lines describe the strings from the set. In the $i$th of them, a single string $s_i$ is given, consisting of lowercase letters of the English alphabet. Denote by $S$ the total length of all strings from the set. It is guaranteed that $S \le 10^6$, as well as that all strings of $s_i$ are different.

In the following lines, queries are entered. The $i$th of them contains two positive integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le |t|$) — the left and right border of the substring $t$ from the $i$-th query.

第一行包含两个正整数 $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$ 的子串的左边界和右边界。

In a single line, print $m$ integers, $i$th of them should be equal to the answers to the $i$th query.

在一行中输出 $m$ 个整数，其中第 $i$ 个整数应等于第 $i$ 个查询的答案。

In the first example, the first query requires the entire string to count the number of substrings that are included in the set. The substrings $[1, 3]$ and $[4, 6]$ coincide with the string "aba". The substrings match with the string "a" $[1, 1]$, $[3, 3]$, $[5, 5]$, $[7, 7]$. The substring $[3, 4]$ matches the string "ac". In total, it turns out that 7 substrings of the string "abacaba" match the strings from the set.

In the second query, a substring from position 1 to position 3 is taken from the source string, this is the string "aba". The string "aba" enters it 1 time, the string "a" enters it 2 times and the string "ac" does not enter it once as a substring. In the third query, a substring from the 2nd to the 7th position is taken from the source string, this is the string "bacaba". The string "aba" is included in it 1 time, the string "a" is included 3 times and the string "ac" is included 1 time as a substring.

在第一个例子中，第一个查询要求对整个字符串进行处理，以统计其中属于给定集合的子串数量。子串 $[1, 3]$ 和 $[4, 6]$ 均与字符串 "aba" 完全一致；子串 $[1, 1]$、$[3, 3]$、$[5, 5]$、$[7, 7]$ 均与字符串 "a" 匹配；子串 $[3, 4]$ 与字符串 "ac" 匹配。总计，字符串 "abacaba" 中有 7 个子串与集合中的字符串匹配。

在第二个查询中，从原字符串中取出位置 1 到位置 3 的子串，即字符串 "aba"。其中，字符串 "aba" 作为子串出现 1 次，字符串 "a" 出现 2 次，而字符串 "ac" 未出现（即出现 0 次）。

在第三个查询中，从原字符串中取出第 2 至第 7 位的子串，即字符串 "bacaba"。其中，字符串 "aba" 作为子串出现 1 次，字符串 "a" 出现 3 次，字符串 "ac" 出现 1 次。