ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4176: 感情的热烈传播

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：6 通过：4
提交提交记录统计Web Board

题目描述

Nadeko的生日快到了! 当她为派对装饰房间时，一个由石竹花形纸片组成的长花环被放置在墙壁的一个显眼部分。Koyomi哥哥会喜欢的！"

但她对花环仍不满意，Nadeko决定再次擦亮它。花环有n块，从左到右从1到n编号，第i块有一个颜色si，用一个小写的英文字母表示。Nadeko最多可以给m个花环重新上色，给每个花环一个任意的新颜色（仍然用一个小写的英文字母表示）。在这项工作之后，她会找出花环中所有只包含颜色为c的碎片的子段--这是Koyomi兄弟最喜欢的颜色，并将其中最长的长度作为花环的Koyomity。

例如，我们假设花环由 "kooomo "表示，而Koyomi兄弟最喜欢的颜色是 "o"。在所有只包含 "o "的子段中，"ooo "是最长的，长度为3，因此这个花环的Koyomity等于3。

但是问题出现了，因为Nadeko不确定Koyomi兄弟最喜欢的颜色，而且对要做的工作的数量有摇摆不定的想法。她对此有七个计划，每个计划都可以用一对整数mi和一个小写字母ci来表示，其含义已在上面说明。你要根据每个计划找出重新粉刷花环后可达到的最大Koyomity。

Nadeko's birthday is approaching! As she decorated the room for the party, a long garland of Dianthus-shaped paper pieces was placed on a prominent part of the wall. Brother Koyomi will like it!

Still unsatisfied with the garland, Nadeko decided to polish it again. The garland has n pieces numbered from 1 to n from left to right, and the i-th piece has a colour si, denoted by a lowercase English letter. Nadeko will repaint at most m of the pieces to give each of them an arbitrary new colour (still denoted by a lowercase English letter). After this work, she finds out all subsegments of the garland containing pieces of only colour c − Brother Koyomi's favourite one, and takes the length of the longest among them to be the Koyomity of the garland.
For instance, let's say the garland is represented by "kooomo", and Brother Koyomi's favourite colour is "o". Among all subsegments containing pieces of "o" only, "ooo" is the longest, with a length of 3. Thus the Koyomity of this garland equals 3.
But problem arises as Nadeko is unsure about Brother Koyomi's favourite colour, and has swaying ideas on the amount of work to do. She has q plans on this, each of which can be expressed as a pair of an integer mi and a lowercase letter ci, meanings of which are explained above. You are to find out the maximum Koyomity achievable after repainting the garland according to each plan.
Input
The first line of input contains a positive integer n (1≤n≤1500) − the length of the garland.
The second line contains n lowercase English letters s1s2... sn as a string − the initial colours of paper pieces on the garland.
The third line contains a positive integer q (1≤q≤200000) − the number of plans Nadeko has.
The next q lines describe one plan each: the i-th among them contains an integer mi (1≤mi≤n) − the maximum amount of pieces to repaint, followed by a space, then by a lowercase English letter ci − Koyomi's possible favourite colour.
Output
Output q lines: for each work plan, output one line containing an integer − the largest Koyomity achievable after repainting the garland according to it.
Examples
Input 
6
koyomi
3
1 o
4 o
4 m
Output 
3
6
5
Input 
15
yamatonadeshiko
10
1 a
2 a
3 a
4 a
5 a
1 b
2 b
3 b
4 b
5 b
Output 
3
4
5
7
8
1
2
3
4
5
Input 
10
aaaaaaaaaa
2
10 b
10 z
Output 
10
10
Note
In the first sample, there are three plans:
  • In the first plan, at most 1 piece can be repainted. Repainting the "y" piece to become "o" results in "kooomi", whose Koyomity of 3 is the best achievable;
  • In the second plan, at most 4 pieces can be repainted, and "oooooo" results in a Koyomity of 6;
  • In the third plan, at most 4 pieces can be repainted, and "mmmmmi" and "kmmmmm" both result in a Koyomity of 5.

输入格式

输入的第一行包含一个正整数n（1≤n≤1500）--花环的长度。

第二行包含n个小写英文字母s1s2...sn作为一个字符串--花环上纸片的初始颜色。

第三行包含一个正整数q（1≤q≤200000）--Nadeko有多少个计划。

接下来的q行分别描述一个计划：其中第i行包含一个整数mi（1≤mi≤n）--要重新绘制的纸片的最大数量，后面是一个空格，然后是一个小写英文字母ci--Koyomi可能喜欢的颜色。

输出格式

对于每个工作计划，输出一行，包含一个整数--根据它重新粉刷花环后可实现的最大Koyomity。

输入样例：

6

koyomi

3

1 o

4 o

4 m

 

输出样例：

3

6

5

 

输入样例：

15

yamatonadeshiko

10

1 a

2 a

3 a

4 a

5 a

1 b

2 b

3 b

4 b

5 b

 

输出样例：

3

4

5

7

8

1

2

3

4

5

 

输入样例：

10

aaaaaaaaaa

2

10 b

10 z

 

输出样例：

10

10

输入样例 复制 

6

koyomi

3

1 o

4 o

4 m

输出样例 复制 

3

6

5

数据范围与提示

在第一个示例中，有三个方案:

在第一种方案中，最多可以重绘1件作品。将“y”重绘为“o”的结果是“kooomi”，其Koyomity为3是最好的;

在第二个方案中，最多可以重绘4件作品，“oooooo”的结果是Koyomity为6;

在第三个方案中，最多可以重绘4件作品，“mmmmmi”和“kmmmmm”都导致Koyomity为5；

分类标签