P17441 打字

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 的最终得分。

对于所有数据，保证 $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$。 | 测试点编号 | $Turn\le$ | $n\le$ | $m\le$ | $\|S\|\le$ | $\sum\|S\|\le$ | $q\le$ | 特殊性质 | 时间限制 | | :--------: | :-------: | :----: | :----: | :--------: | :------------: | :----: | :---------: | ----------- | | $1$ | $300$ | $16$ | $63$ | $10^5$ | $3\times10^5$ | $0$ | $\text{A}$ | $1\text{s}$ | | $2$ | $300$ | $16$ | $1$ | $10^5$ | $3\times10^5$ | $0$ | 无 | $1\text{s}$ | | $3$ | $39$ | $3$ | $2$ | $3$ | $102$ | $0$ | $\text{BD}$ | $1\text{s}$ | | $4$ | $81$ | $3$ | $2$ | $4$ | $324$ | $0$ | $\text{BD}$ | $1\text{s}$ | | $5$ | $243$ | $3$ | $2$ | $5$ | $1215$ | $0$ | $\text{BD}$ | $1\text{s}$ | | $6$ | $300$ | $3$ | $2$ | $10$ | $3000$ | $0$ | $\text{B}$ | $1\text{s}$ | | $7\sim10$ | $300$ | $3$ | $2$ | $10^5$ | $3\times10^5$ | $0$ | $\text{B}$ | $1\text{s}$ | | $11$ | $300$ | $5$ | $63$ | $10^5$ | $3\times10^5$ | $0$ | 无 | $1\text{s}$ | | $12$ | $300$ | $10$ | $63$ | $10^5$ | $3\times10^5$ | $0$ | 无 | $1\text{s}$ | | $13\sim14$ | $300$ | $16$ | $63$ | $10^5$ | $3\times10^5$ | $0$ | 无 | $1\text{s}$ | | $15\sim16$ | $1000$ | $63$ | $63$ | $10^6$ | $2\times10^6$ | $0$ | 无 | $4\text{s}$ | | $17\sim18$ | $1000$ | $63$ | $63$ | $10^6$ | $2\times10^6$ | $30$ | $\text{C}$ | $4\text{s}$ | | $19\sim20$ | $1000$ | $63$ | $63$ | $10^6$ | $2\times10^6$ | $30$ | 无 | $8\text{s}$ | 性质 $\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}$ 优化。