题目描述

Igallta 和弥儿在玩游戏。

她们先约定好两个和游戏有趣程度有关的系数 $n$ 和 $m$，再约定好了一个字符串 $S$，该字符串只有可能出现字符串 $\Sigma=\texttt{abcdefghijklmnopqrstuvwxyz\_ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789}$ 的前 $n$ 个字符。

露薇娅给她们带来了一个打字机，Igallta 作为打字的一方，而弥儿则作为控制打字机的一方。

打字机连接着一个显示器，Igallta 和弥儿都可以看到显示器上的字符串 $T$，表示 Igallta 打出的字符串。打字机有 $n+1$ 个按键。有 $n$ 个按键分别对应了 $\Sigma$ 的前 $n$ 个字符，称为字符键，按下字符键就会在 $T$ 的末尾出现该字符键对应的字符；另外 $1$ 个按键为删除键，按下删除键就会把 $T$ 的最后一个字符删除，如果 $T$ 已经为空串就不会发生任何事情。

仅仅是这样的话太没意思了，因此露薇娅把 $n$ 个字符键上面的字符消去，并且随机打乱，这样 Igallta 一开始就不知道按下一个字符键会在字符串 $T$ 后面出现什么字符，除非她按下这个字符键，这样她才能确定这个字符键对应了什么字符。

然而这样 Igallta 依然可以很快知道字符键对应的字符，因此 Igallta 每按下 $m$ 次字符键之后，弥儿就会把这 $n$ 个字符键再次随机打乱，这样 Igallta 就又不知道字符键对应的字符了。注意 Igallta 可以在任意时候按任意次删除键，这不会被计入按下字符键的次数。

特别地，当 Igallta 尝试按下一个字符键之后，弥儿可以任意决定这个字符键对应的字符，只要它不和之前 Igallta 获取到的信息矛盾，这点类似于自适应的交互库。

Igallta 可以在任意时候结束游戏，并计算她在本轮游戏的得分。但是当 Igallta 按下字符键和删除键的总次数达到 $79^{37^{77}}$ 次的时候，游戏将自动结束。如果最终她打出的字符串 $T$ 不是 $S$ 的一个子序列，那么她的得分为 $-80^{73^{75}}$，否则她的得分为字符串 $T$ 的长度。

Igallta 想要最大化自己的得分，而弥儿想要最小化 Igallta 的得分。弥儿作为“穿越时空的猎犬”，Igallta 作为新一代人工智能，她们都可以做出最正确的抉择。

现在露薇娅知道了 $n,m$ 和 $S$，她想知道双方都采取最优策略的情况下 Igallta 的最终得分。（容易证明在双方都采取最优策略的情况下 Igallta 的最终得分不会是 $-80^{73^{75}}$）

然而约定一次合理且有趣的游戏是很麻烦的，为了增加游戏的轮数，有时候 Igallta 和弥儿还会给出 $1\le l\le r\le|S|$（其中 $|S|$ 表示字符串 $S$ 的长度），并选出 $S$ 的一段子串 $S_{l\sim r}$ 进行游戏。即在计算分数时，如果 $T$ 不是 $S_{l\sim r}$ 的子序列，Igallta 的得分为 $-80^{73^{75}}$，否则 Igallta 的得分为 $|T|$。

注意本题中字符串是从 $1$ 开始标号的。

注：称 $T$ 是 $S$ 的子序列当且仅当删除 $S$ 某些位置的字符（可以不删除，也可以全部删除），并将剩下的字符按原顺序拼接可以得到 $T$，如 aad、aaead、aadead 都是 aadead 的子序列，而 eda、aaaa、c 不是 aadead 的子序列。依照定义可知，空串是所有字符串的子序列。

$S_{l\sim r}$ 是指字符串 $S$ 的第 $l$ 个字符到第 $r$ 个字符按原顺序拼接得到的字符串。

输入格式

第一行两个正整数 $Tid,Turn$，分别表示测试点编号、数据组数。对于样例，$Tid$ 表示其满足第 $Tid$ 个测试点的限制。

接下来有 $Turn$ 组数据，对于每组数据，第一行有三个正整数 $n,m,|S|$，和一个非负整数 $q$，第二行有一个长度为 $|S|$ 的仅包含 $\Sigma$ 的前 $n$ 个字符的字符串 $S$，表示初始的游戏中约定好的字符串。接下来有 $q$ 行，每行两个正整数 $l,r$，表示一次询问。

输出格式

对于每组数据输出一行 $q+1$ 个非负整数，第 $1$ 个数表示初始的游戏中，双方都采取最优策略时 Igallta 的最终得分，第 $i$（$i>1$）个数表示在第 $i-1$ 次询问选出的子串中进行游戏，双方都采取最优策略时 Igallta 的最终得分。

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

提示

对于所有数据，保证 $1\le n,m\le 63,1\le Turn\le1000,0\le q \le 30$，保证 $1\le l\le r\le|S|\le10^6$，保证 $\sum|S|\le 2\times 10^6$。

性质 $\text{A}$：保证 $m\ge n$。

性质 $\text{B}$：保证 $n=3$，并且 $m=2$。

性质 $\text{C}$：保证数据以下述方式随机生成。

先确定 $Tid$ 和 $Turn$，接下来随机生成 $Turn$ 组数据。$Turn$ 组数据的生成都是相互独立的。

在每组测试数据中，先确定 $n,m,|S|,q$，而后字符串 $S$ 在所有可能的字符串中均匀随机生成，并且每组询问的 $l,r$ 也在所有可能的 $l,r$ 中均匀随机生成。字符串 $S$ 与每组询问的 $l,r$ 的生成也都是相互独立的。

性质 $\text{D}$：该测试点的输入文件下发，在附件下载处可找到该测试点的输入文件 type*.in。

输入文件最大大约有 $2.1\text{MB}$，请使用较快的输入方式。在下发文件中包含了 fastread.cpp，可以直接使用。

请选手注意常数优化。

样例解释：

对于第五组样例表示的游戏，以下是可能的一种游戏过程：

1. Igallta 按下第一个字符键，得到 c。
2. Igallta 按下一次删除键，并按下第二个字符键，得到 b。弥儿把按键重新打乱。
3. Igallta 按下第二个字符键，得到 c。
4. Igallta 按下第三个字符键，得到 a。弥儿把按键重新打乱。此时 $T=\texttt{bca}$。
5. Igallta 按下第一个字符键，得到 c。
6. Igallta 按下第三个字符键，得到 b。弥儿把按键重新打乱。
7. Igallta 结束游戏，此时 $T=\texttt{bcacb}$，她的得分为 $5$。

对于第五组样例的第一个询问，以下是可能的一种游戏过程：

1. Igallta 按下第一个字符键，得到 b。
2. Igallta 按下第二个字符键，得到 a。弥儿把按键重新打乱。
3. 此时 $T=\texttt{ba}$，不是 $S_{1\sim3}=\texttt{abc}$ 的子序列，如果此时 Igallta 选择结束游戏，她的得分将是 $-80^{73^{75}}$。于是她按下一次删除键，此时 $T=\texttt{b}$。
4. Igallta 按下第一个字符键，得到 a。
5. Igallta 按下一次删除键，此时 $T=\texttt{b}$。
6. Igallta 按下第三个字符键，得到 b。弥儿把按键重新打乱。
7. Igallta 按下一次删除键并结束游戏，此时 $T=\texttt{b}$，她的得分为 $1$。

评测限制：

时间限制：$1\sim 8\text{s}$。

空间限制：$1024\text{MB}$。

评测模式：开启 $\text{O2}$ 优化。

Idea：2021CHD & fydj，Solution：fydj & 2021CHD，Code：fydj & 2021CHD，Data：fydj & 2021CHD