Background

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

Problem Description

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.

Input Format

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$.

Output Format

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).

7 3
popoqqq
1 4
2 3 5
4 1 2 5 6

0
0
2

Hint

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