抚子的生日快到了!当她为聚会装饰房间时,在墙壁的显着位置放置了一个由石竹形状的纸片制成的长花环。历兄一定会喜欢的!
抚子对花环仍然不满意,决定再次打磨它。花环有n片,从左到右编号为1到n,第i片颜色为si,用小写英文字母表示。 Nadeko 最多会重新绘制 m 个碎片,为每个碎片赋予任意的新颜色(仍然用小写英文字母表示)。完成这项工作后,她找出了花环中仅包含历兄最喜欢的颜色c的碎片的所有子段,并取其中最长的长度作为花环的Koyomity。
举例来说,假设花环是“kooomo”,而历哥哥最喜欢的颜色是“o”。在所有仅包含“o”片段的子段中,“ooo”是最长的,长度为 3。因此,该花环的 Koyomity 等于 3。
但问题出现了,因为抚子不确定历兄最喜欢的颜色,并且对要做的工作量有摇摆不定的想法。她对此有q个计划,每个计划都可以表示为一对整数mi和小写字母ci,其含义如上所述。您需要找出根据每个计划重新绘制花环后可实现的最大 Koyomity。
输入
输入的第一行包含一个正整数 n (1 ≤ n ≤ 1 500) — 花环的长度。
第二行包含n个小写英文字母s1s2... sn作为字符串——花环上纸片的初始颜色。
第三行包含一个正整数 q (1 ≤ q ≤ 200 000) — Nadeko 的计划数量。
接下来的 q 行每行描述一个计划:其中第 i 行包含一个整数 mi (1 ≤ mi ≤ n) — 要重新绘制的最大块数,后跟一个空格,然后是一个小写英文字母 ci — Koyomi 可能最喜欢的颜色。
输出
输出q行:对于每个工作计划,输出一行包含一个整数——根据它重新绘制花环后可实现的最大Koyomity。
示例
输入 #1
6 koyomi 3 1 o 4 o 4 m
输出 #1
3 6 5
输入 #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 件。将“y”部分重新绘制为“o”会产生“kooomi”,其 Koyomity 为 3 是可实现的最佳效果;
- 在第二个计划中,最多可以重新绘制 4 件,“oooooo”导致 Koyomity 为 6;
- 在第三个计划中,最多可以重新绘制 4 件,“mmmmmi”和“kmmmmm”的 Koyomity 均为 5。