Problem Description

Igallta and Mi'er are playing a game.

First, they agree on two coefficients $n$ and $m$ related to how interesting the game is, and then they agree on a string $S$. This string contains only characters from the first $n$ characters of $\Sigma=\texttt{abcdefghijklmnopqrstuvwxyz\_ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789}$.

Luvia brings them a typewriter. Igallta is the one who types, and Mi'er is the one who controls the typewriter.

The typewriter is connected to a monitor. Both Igallta and Mi'er can see the string $T$ on the monitor, which represents what Igallta has typed. The typewriter has $n+1$ keys. Among them, $n$ keys correspond to the first $n$ characters of $\Sigma$; these are called character keys. Pressing a character key appends the corresponding character to the end of $T$. The remaining key is a delete key; pressing it deletes the last character of $T$. If $T$ is already empty, nothing happens.

This alone is too boring, so Luvia removes the labels on the $n$ character keys and shuffles them randomly. As a result, at the beginning Igallta does not know what character will be appended to $T$ when she presses a particular character key, unless she presses that key, in which case she can determine which character that key corresponds to.

However, Igallta could still learn the mapping quickly, so after Igallta presses character keys $m$ times, Mi'er will randomly shuffle these $n$ character keys again. Then Igallta no longer knows the mapping. Note that Igallta may press the delete key any number of times at any moment, and these do not count toward the number of character key presses.

In particular, when Igallta attempts to press a character key, Mi'er may decide arbitrarily what character that key corresponds to, as long as it does not contradict the information Igallta has obtained before. This is similar to an adaptive interactive judge.

Igallta may end the game at any time and compute her score for this round. However, when the total number of presses of character keys and the delete key reaches $79^{37^{77}}$, the game will end automatically. If the final typed string $T$ is not a subsequence of $S$, then her score is $-80^{73^{75}}$; otherwise, her score is the length of $T$.

Igallta wants to maximize her score, while Mi'er wants to minimize Igallta's score. Mi'er, as a “time-traveling hound”, and Igallta, as a new-generation artificial intelligence, can both make the optimal choices.

Now Luvia knows $n$, $m$, and $S$, and she wants to know Igallta’s final score when both sides use optimal strategies. (It is easy to prove that under optimal play, Igallta’s final score will not be $-80^{73^{75}}$.)

However, agreeing on a reasonable and interesting game each time is troublesome. To increase the number of rounds, sometimes Igallta and Mi'er also give $1\le l\le r\le|S|$ (where $|S|$ is the length of $S$) and choose a substring $S_{l\sim r}$ of $S$ to play the game. That is, when computing the score, if $T$ is not a subsequence of $S_{l\sim r}$, then Igallta’s score is $-80^{73^{75}}$; otherwise, Igallta’s score is $|T|$.

Note that in this problem, strings are indexed starting from $1$.

Note: $T$ is called a subsequence of $S$ if and only if by deleting some characters of $S$ at certain positions (possibly deleting none, or deleting all), and concatenating the remaining characters in the original order, we can obtain $T$. For example, aad, aaead, aadead are all subsequences of aadead, while eda, aaaa, c are not subsequences of aadead. By definition, the empty string is a subsequence of every string.

$S_{l\sim r}$ refers to the string formed by concatenating the $l$-th to the $r$-th characters of $S$ in order.

Input Format

The first line contains two positive integers $Tid,Turn$, representing the test point ID and the number of test groups. For the samples, $Tid$ indicates that the sample satisfies the constraints of test point $Tid$.

Then there are $Turn$ groups of testdata. For each group, the first line contains three positive integers $n,m,|S|$, and a non-negative integer $q$. The second line contains a string $S$ of length $|S|$ consisting only of the first $n$ characters of $\Sigma$, representing the string agreed upon in the initial game. Then follow $q$ lines, each containing two positive integers $l,r$, representing one query.

Output Format

For each test group, output one line of $q+1$ non-negative integers. The $1$-st number is Igallta’s final score in the initial game when both sides play optimally. The $i$-th number ($i>1$) is Igallta’s final score when playing the game on the substring chosen in the $(i-1)$-th query, with both sides playing optimally.

20 9
1 1 3 0
aaa
2 1 2 0
ab
3 3 8 0
abcabcab
3 2 5 0
aabcc
3 2 8 1
abcabcab
1 3
2 1 9 0
aabbaabba
4 3 9 0
abcddcbdd
14 10 10 0
ediahgnehc
21 17 11 0
ediauhgnehc

3
1
8
1
5 1
4
4
3
4

Hint

For all data, it is guaranteed that $1\le n,m\le 63$, $1\le Turn\le1000$, $0\le q \le 30$. It is guaranteed that $1\le l\le r\le|S|\le10^6$, and $\sum|S|\le 2\times 10^6$.

Property $\text{A}$: It is guaranteed that $m\ge n$.

Property $\text{B}$: It is guaranteed that $n=3$ and $m=2$.

Property $\text{C}$: It is guaranteed that the data is randomly generated in the following way.

First, determine $Tid$ and $Turn$, then randomly generate $Turn$ groups of testdata. The generation of the $Turn$ groups is independent of each other.

In each test group, first determine $n,m,|S|,q$, then the string $S$ is generated uniformly at random among all possible strings, and each query’s $l,r$ is also generated uniformly at random among all possible $l,r$. The generation of $S$ and the generation of each query’s $l,r$ are also independent of each other.

Property $\text{D}$: The input file for this test point is provided and can be found in the attachment download area as type*.in.

The maximum size of the input file is about $2.1\text{MB}$. Please use a fast input method. The provided files include fastread.cpp, which can be used directly.

Please pay attention to constant-factor optimization.

Sample explanation:

For the game represented by the fifth sample group, the following is one possible process:

1. Igallta presses the first character key and gets c.
2. Igallta presses the delete key once, then presses the second character key and gets b. Mi'er shuffles the keys again.
3. Igallta presses the second character key and gets c.
4. Igallta presses the third character key and gets a. Mi'er shuffles the keys again. Now $T=\texttt{bca}$.
5. Igallta presses the first character key and gets c.
6. Igallta presses the third character key and gets b. Mi'er shuffles the keys again.
7. Igallta ends the game. Now $T=\texttt{bcacb}$, and her score is $5$.

For the first query of the fifth sample group, the following is one possible process:

1. Igallta presses the first character key and gets b.
2. Igallta presses the second character key and gets a. Mi'er shuffles the keys again.
3. Now $T=\texttt{ba}$, which is not a subsequence of $S_{1\sim3}=\texttt{abc}$. If Igallta chooses to end the game now, her score would be $-80^{73^{75}}$. So she presses the delete key once, and now $T=\texttt{b}$.
4. Igallta presses the first character key and gets a.
5. Igallta presses the delete key once, and now $T=\texttt{b}$.
6. Igallta presses the third character key and gets b. Mi'er shuffles the keys again.
7. Igallta presses the delete key once and ends the game. Now $T=\texttt{b}$, and her score is $1$.

Judging limits:

Time limit: $1\sim 8\text{s}$.

Memory limit: $1024\text{MB}$.

Judging mode: $\text{O2}$ optimization enabled.

Idea: 2021CHD & fydj, Solution: fydj & 2021CHD, Code: fydj & 2021CHD, Data: fydj & 2021CHD.

Translated by ChatGPT 5