CF814C An impassioned circulation of affection

Nadeko 的生日快到了！当她为派对装饰房间时，一条由康乃馨形状纸片组成的长彩带被挂在了墙上最显眼的位置。Koyomi 哥哥一定会喜欢的！ Nadeko 觉得彩带还不够完美，决定再加工一下。彩带由 $n$ 个纸片从左到右顺序编号 $1$ 到 $n$，第 $i$ 个纸片的颜色为 $s_i$，用一个小写英文字母表示。Nadeko 可以最多重新粉刷 $m$ 个纸片，把每个纸片粉刷成任意一种新颜色（同样用小写英文字母表示）。粉刷完后，她会找出所有只包含颜色 $c$ 的连续子段（$c$ 是 Koyomi 哥哥最喜欢的颜色），并记录其中最长连续子段的长度，称之为彩带的 “Koyomity”。 例如，假设彩带为 "kooomo"，Koyomi 哥哥最喜欢的颜色是 "o"。在所有只包含 "o" 的子段中，"ooo" 是最长的，其长度为 $3$。因此，该彩带的 Koyomity 为 $3$。 但问题来了，Nadeko 不确定哥哥最喜欢什么颜色，也对要做多少工作拿不定主意。她有 $q$ 个计划，每个计划可以用整数 $m_i$ 和小写字母 $c_i$ 的组合表示，如上所述。你需要针对每个计划，计算粉刷后最多可以获得的 Koyomity。

第一行包含一个正整数 $n$（$1 \le n \le 1500$），表示彩带的长度。 第二行包含 $n$ 个小写英文字母 $s_{1}s_{2}\ldots s_{n}$，表示彩带纸片的初始颜色。 第三行包含一个正整数 $q$（$1 \le q \le 200000$），表示计划的数量。 接下来 $q$ 行，每行描述一个计划：第 $i$ 行包含一个整数 $m_i$（$1 \le m_i \le n$），表示最多粉刷的纸片数，后跟一个空格，再跟一个小写英文字母 $c_i$，表示 Koyomi 可能最喜欢的颜色。

输出 $q$ 行，对于每个计划输出一行，表示在按照该计划粉刷后，可以获得的最大 Koyomity。

在第一个样例中，有三个计划： - 第一个计划最多能粉刷 $1$ 个纸片，将 "y" 粉刷成 "o" 得到 "kooomi"，其 Koyomity 最优为 $3$； - 第二个计划最多能粉刷 $4$ 个纸片，可以全部变成 "oooooo"，Koyomity 为 $6$； - 第三个计划最多能粉刷 $4$ 个纸片，"mmmmmi" 和 "kmmmmm" 都可以得到 Koyomity $5$。 由 ChatGPT 5 翻译