### 问题描述 给定一个集合 $S$ ，其中有 $n$ 个元素，求出此集合所有子集元素之和。 某天小蓝同学过生日，同学们都去给小蓝同学庆祝生日了，并出了一道题，只要小蓝同学正确解出，就可以获得惊喜礼物，这道题是这样的：对于一个字符串 $s$ 对于字符 $c$ 的权值，定义为 $s$ 中仅由 $c$ 组成的最长连续子串的长度。例如 $bookoooo$ ，其中由字符 $o$ 组成的最长长度就是4(串 $oooo$ 是最长连续为 $o$ 的，且长度为4)。 现在给定一个字符串 $s$ 以及 $q$ 个询问。每个询问形如 $(m_i , c_i)$ 的形式，表示求出在 $s$ 中至多更改 $m_i$ 个位置的字符后所得的字符串 $s'$ 对于字符 $c_i$ 的最大权值。 小蓝同学很想得到惊喜礼物，听说你很会解题，他只能求助于你。 ### 输入格式 第一行包含一个正整数 $n$ ，代表字符串$s$的长度。 第二行包含 $n$ 个小写的英文字母组成的字符串 $s_1$ , $s_2$ , ... , $s_n$ 组成初始的字符串。 第三行包含一个正整数 $q$ ，代表询问的数目。 接下来$q$行，每行两个以空格分隔的正整数 $m_i$ , $c_i$ 分别代表至多更改的字符数目，以及询问更改后 $s'$ 字符串对于字符 $c_i$ 的最大权值是多少。 ### 输出格式 其中每组输出 $q$ 行，每个询问包含一行，一行一个整数，代表更改后的字符串 $s'$ 中字符 $c_i$ 的最大权值。 ### 样例输入 ```text 15 yamatonadeshiko 10 1 a 2 a 3 a 4 a 5 a 1 b 2 b 3 b 4 b 5 b ``` ### 样例输出 ```text 3 4 5 7 8 1 2 3 4 5 ``` ### 评测数据规模 对于所有评测数据， $1 \leq n \leq 1500$ ， $1 \leq q \leq 2 \times 10^5 $，$1 \leq m_i \leq n$，$c_i$ 为小写字母。