1410: #6092. 「Codeforces Round #418」恋爱循环

Memory Limit:256 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

セーノ
预备、起

字符串 sss 对于字符 ccc 的权值,定义为 sss 中仅由 ccc 组成的最长连续子串的长度。例如,对于 s=kooomio,其由字符 o 组成的最长连续子串为 ooo,因此它对于字符 o 的权值为 333

给定由小写字母组成的字符串 sss 以及 qqq 个询问。每个询问形如 (mi,ci)(m_i, c_i)(mi,ci),表示「求出在 sss至多更改 mim_imi 个位置的字符后所得的字符串 s′s's 对于字符 cic_ici 的最大权值」。

输入格式

输入的第一行包含一个正整数 nnn —— 字符串 sss 的长度。

第二行包含 nnn 个小写英文字母组成的字符串 s1s2…sns_{1} s_2 \ldots s_ns1s2sn —— 给定的初始字符串。

第三行包含一个正整数 qqq —— 询问的数目。

接下来 qqq 行,每行包含一个正整数 mim_imi —— 至多在 sss 中更改的字符数目,和以一个空格分隔的小写字母 mim_imi —— 计算权值时使用的字符。

输出格式

输出 qqq 行:对于每个询问输出一行,包含一个整数 —— 进行更改后所得字符串 s′s's 的最大权值。

样例

样例输入 1

6
koyomi
3
1 o
4 o
4 m

样例输出 1

3
6
5

样例解释 1

在样例 1 中,有三个询问:

  • 在第一个询问中,最多可以更改 sss 一个位置上的字符,将 y 所处的位置改为 o 得到 s=kooomi,权值为 333
  • 在第二个询问中,最多可以更改 sss 四个位置上的字符,s=oooooo 的权值为 666
  • 在第三个询问中,最多可以更改 sss 四个位置上的字符,s=mmmmmis=kmmmmm 的权值均为 555

样例输入 2

15
yamatonadeshiko
10
1 a
2 a
3 a
4 a
5 a
1 b
2 b
3 b
4 b
5 b

样例输出 2

3
4
5
7
8
1
2
3
4
5

样例输入 3

10
aaaaaaaaaa
2
10 b
10 z

样例输出 3

10
10

数据范围与提示

1≤n≤15001 \leq n \leq 1\,5001n1500
1≤q≤2000001 \leq q \leq 200\,0001q200000
1≤mi≤n1 \leq m_i \leq n1mincic_ici 为小写英文字母

コイスル キセツハ ヨクバリ サーキュレーション
恋爱的季节是激情洋溢的循环
コイスル キモチハ ヨクバリ サーキュレーション
恋爱的心情是激情洋溢的循环
            ——「恋愛サーキュレーション」