CF1073G.Yet Another LCP Problem

Let $\text{LCP}(s, t)$ be the length of the longest common prefix of strings $s$ and $t$. Also let $s[x \dots y]$ be the substring of $s$ from index $x$ to index $y$ (inclusive). For example, if $s = $ "abcde", then $s[1 \dots 3] =$ "abc", $s[2 \dots 5] =$ "bcde".

You are given a string $s$ of length $n$ and $q$ queries. Each query is a pair of integer sets $a_1, a_2, \dots, a_k$ and $b_1, b_2, \dots, b_l$. Calculate $\sum\limits_{i = 1}^{i = k} \sum\limits_{j = 1}^{j = l}{\text{LCP}(s[a_i \dots n], s[b_j \dots n])}$ for each query.

设 $\text{LCP}(s, t)$ 表示字符串 $s$ 与 $t$ 的最长公共前缀的长度。同时，令 $s[x \dots y]$ 表示字符串 $s$ 中从下标 $x$ 到下标 $y$（含端点）的子串。例如，若 $s = $ "abcde"，则 $s[1 \dots 3] =$ "abc"，$s[2 \dots 5] =$ "bcde"。

给定一个长度为 $n$ 的字符串 $s$ 以及 $q$ 个查询。每个查询由两个整数集合组成：$a_1, a_2, \dots, a_k$ 和 $b_1, b_2, \dots, b_l$。对每个查询，计算 $\sum\limits_{i = 1}^{i = k} \sum\limits_{j = 1}^{j = l}{\text{LCP}(s[a_i \dots n], s[b_j \dots n])}$。

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the length of string $s$ and the number of queries, respectively.

The second line contains a string $s$ consisting of lowercase Latin letters ($|s| = n$).

Next $3q$ lines contains descriptions of queries — three lines per query. The first line of each query contains two integers $k_i$ and $l_i$ ($1 \le k_i, l_i \le n$) — sizes of sets $a$ and $b$ respectively.

The second line of each query contains $k_i$ integers $a_1, a_2, \dots a_{k_i}$ ($1 \le a_1 \lt a_2 \lt \dots \lt a_{k_i} \le n$) — set $a$.

The third line of each query contains $l_i$ integers $b_1, b_2, \dots b_{l_i}$ ($1 \le b_1 \lt b_2 \lt \dots \lt b_{l_i} \le n$) — set $b$.

It is guaranteed that $\sum\limits_{i = 1}^{i = q}{k_i} \le 2 \cdot 10^5$ and $\sum\limits_{i = 1}^{i = q}{l_i} \le 2 \cdot 10^5$.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）—— 分别为字符串 $s$ 的长度和查询次数。

第二行包含一个由小写拉丁字母组成的字符串 $s$（$|s| = n$）。

接下来的 $3q$ 行描述了所有查询，每个查询占三行。每个查询的第一行包含两个整数 $k_i$ 和 $l_i$（$1 \le k_i, l_i \le n$）—— 分别为集合 $a$ 和 $b$ 的大小。

每个查询的第二行包含 $k_i$ 个整数 $a_1, a_2, \dots, a_{k_i}$（$1 \le a_1 \lt a_2 \lt \dots \lt a_{k_i} \le n$）—— 集合 $a$。

每个查询的第三行包含 $l_i$ 个整数 $b_1, b_2, \dots, b_{l_i}$（$1 \le b_1 \lt b_2 \lt \dots \lt b_{l_i} \le n$）—— 集合 $b$。

保证 $\sum\limits_{i = 1}^{i = q}{k_i} \le 2 \cdot 10^5$ 且 $\sum\limits_{i = 1}^{i = q}{l_i} \le 2 \cdot 10^5$。

Print $q$ integers — answers for the queries in the same order queries are given in the input.

输出 $q$ 个整数——按输入中查询出现的相同顺序，依次输出各查询的答案。

Description of queries:

1. In the first query $s[1 \dots 7] = \text{abacaba}$ and $s[2 \dots 7] = \text{bacaba}$ are considered. The answer for the query is $\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{bacaba}) + \text{LCP}(\text{bacaba}, \text{abacaba}) + \text{LCP}(\text{bacaba}, \text{bacaba}) = 7 + 0 + 0 + 6 = 13$.
2. In the second query $s[1 \dots 7] = \text{abacaba}$, $s[2 \dots 7] = \text{bacaba}$, $s[3 \dots 7] = \text{acaba}$ and $s[7 \dots 7] = \text{a}$ are considered. The answer for the query is $\text{LCP}(\text{abacaba}, \text{a}) + \text{LCP}(\text{bacaba}, \text{a}) + \text{LCP}(\text{acaba}, \text{a}) = 1 + 0 + 1 = 2$.
3. In the third query $s[1 \dots 7] = \text{abacaba}$ are compared with all suffixes. The answer is the sum of non-zero values: $\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{acaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{abacaba}, \text{a}) = 7 + 1 + 3 + 1 = 12$.
4. In the fourth query $s[1 \dots 7] = \text{abacaba}$ and $s[5 \dots 7] = \text{aba}$ are considered. The answer for the query is $\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{aba}, \text{abacaba}) + \text{LCP}(\text{aba}, \text{aba}) = 7 + 3 + 3 + 3 = 16$.

查询描述：

1. 在第一个查询中，考虑子串 $s[1 \dots 7] = \text{abacaba}$ 和 $s[2 \dots 7] = \text{bacaba}$。该查询的答案为 $\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{bacaba}) + \text{LCP}(\text{bacaba}, \text{abacaba}) + \text{LCP}(\text{bacaba}, \text{bacaba}) = 7 + 0 + 0 + 6 = 13$。
2. 在第二个查询中，考虑子串 $s[1 \dots 7] = \text{abacaba}$、$s[2 \dots 7] = \text{bacaba}$、$s[3 \dots 7] = \text{acaba}$ 和 $s[7 \dots 7] = \text{a}$。该查询的答案为 $\text{LCP}(\text{abacaba}, \text{a}) + \text{LCP}(\text{bacaba}, \text{a}) + \text{LCP}(\text{acaba}, \text{a}) = 1 + 0 + 1 = 2$。
3. 在第三个查询中，将 $s[1 \dots 7] = \text{abacaba}$ 与所有后缀进行比较。答案为所有非零值之和：$\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{acaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{abacaba}, \text{a}) = 7 + 1 + 3 + 1 = 12$。
4. 在第四个查询中，考虑子串 $s[1 \dots 7] = \text{abacaba}$ 和 $s[5 \dots 7] = \text{aba}$。该查询的答案为 $\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{aba}, \text{abacaba}) + \text{LCP}(\text{aba}, \text{aba}) = 7 + 3 + 3 + 3 = 16$。