P7409 SvT

(I do not want to tell you what the problem name is supposed to mean.)

You are given a string $S$ of length $n$ that contains only lowercase letters, with indices in $[1,n]$. Now there are multiple queries. For each query, we are given several suffixes (represented by their starting positions in $S$). Find the sum of the LCP (Longest Common Prefix) lengths over all unordered pairs among these suffixes. The LCP length of a pair of suffixes is counted only once.

The first line contains two positive integers $n,m$, representing the length of $S$ and the number of queries. The next line contains a string $S$. Then follow $m$ queries. For each query, the following format is given on one line: First an integer $t$, meaning there are $t$ suffixes. Then $t$ integers follow, each indicating the starting position of one suffix in the string $S$.

For each query, output one integer per line, representing the answer to that query. Since the answer may be very large, you only need to output the remainder of the answer modulo $\text{23333333333333333}$ (a huge prime).

Sample explanation: For query 1, there is only one suffix `oqqq`, so the answer is $0$. For query 2, there are two suffixes `poqqq` and `qqq`. Their LCP is $0$, so the answer is $0$. For query 3, there are four suffixes `popoqqq`, `opoqqq`, `qqq`, `qq`. Only the pair `qqq` and `qq` has a non-zero LCP, with length $2$, so the answer is $2$. Constraints: For $100\%$ of the testdata, $|S|\le 5\times 10^5$, and $\sum t\le 3\times10^6$. Special note: Due to changes in some parameters in another world line, for a query, even if a suffix appears multiple times, it is counted only once. Source: bzoj 3879. Translated by ChatGPT 5