题目描述

セーノ
预备、起

字符串 $s$ 对于字符 $c$ 的权值，定义为 $s$ 中仅由 $c$ 组成的最长连续子串的长度。例如，对于 $s = \texttt{kooomio}$，其由字符 $\texttt{o}$ 组成的最长连续子串为 $\texttt{ooo}$，因此它对于字符 $\texttt{o}$ 的权值为 $3$。

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

输入格式

输入的第一行包含一个正整数 $n$ —— 字符串 $s$ 的长度。

第二行包含 $n$ 个小写英文字母组成的字符串 $s_{1} s_2 \ldots s_n$ —— 给定的初始字符串。

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

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

输出格式

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

样例 1

input

6
koyomi
3
1 o
4 o
4 m

output

3
6
5

在样例 1 中，有三个询问：

• 在第一个询问中，最多可以更改 $s$ 一个位置上的字符，将 $\texttt{y}$ 所处的位置改为 $\texttt{o}$ 得到 $s' = \texttt{kooomi}$，权值为 $3$；
• 在第二个询问中，最多可以更改 $s$ 四个位置上的字符，$s' = \texttt{oooooo}$ 的权值为 $6$；
• 在第三个询问中，最多可以更改 $s$ 四个位置上的字符，$s' = \texttt{mmmmmi}$ 和 $s' = \texttt{kmmmmm}$ 的权值均为 $5$。

样例 2

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

样例 3

input

10
aaaaaaaaaa
2
10 b
10 z

output

10
10

数据范围与提示

$1 \leq n \leq 1\,500$
$1 \leq q \leq 200\,000$
$1 \leq m_i \leq n$，$c_i$ 为小写英文字母

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