English · Original
Chinese · Translation
Formal · Original
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 _s__i_, 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 _m__i_ and a lowercase letter _c__i_, 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_ ≤ 1 500) — the length of the garland.
The second line contains _n_ lowercase English letters _s_1_s_2... _s__n_ as a string — the initial colours of paper pieces on the garland.
The third line contains a positive integer _q_ (1 ≤ _q_ ≤ 200 000) — the number of plans Nadeko has.
The next _q_ lines describe one plan each: the _i_\-th among them contains an integer _m__i_ (1 ≤ _m__i_ ≤ _n_) — the maximum amount of pieces to repaint, followed by a space, then by a lowercase English letter _c__i_ — 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.
[samples]
## 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.
Nadeko 的生日快到了！她在为派对装饰房间时，将一条由 Dianthus 形状纸片组成的长花环放在了墙上的显眼位置。哥哥 Koyomi 一定会喜欢！
但 Nadeko 对花环仍不满意，决定再打磨一次。这条花环有 #cf_span[n] 个纸片，从左到右编号为 #cf_span[1] 到 #cf_span[n]，第 #cf_span[i] 个纸片的颜色为 #cf_span[si]，用一个小写英文字母表示。Nadeko 将最多 repaint *#cf_span[m]* 个纸片，为每个纸片赋予任意新的颜色（仍用小写英文字母表示）。完成这项工作后，她找出花环中所有仅包含颜色 #cf_span[c] 的子段——这是哥哥 Koyomi 最喜欢的颜色，并取其中最长的长度作为花环的 #cf_span(class=[tex-font-style-underline], body=[Koyomity])。
例如，假设花环表示为 "_kooomo_"，而 Koyomi 最喜欢的颜色是 "_o_"。在所有仅包含 "_o_" 的子段中，"_ooo_" 是最长的，长度为 #cf_span[3]。因此，该花环的 #cf_span(class=[tex-font-style-underline], body=[Koyomity]) 等于 #cf_span[3]。
但问题在于，Nadeko 不确定 Koyomi 最喜欢的颜色，且对需要做的工作量也犹豫不决。她为此制定了 #cf_span[q] 个计划，每个计划可表示为一个整数 #cf_span[mi] 和一个小写字母 #cf_span[ci] 的组合，含义如上所述。你需要对每个计划，求出在根据该计划重新染色花环后所能达到的最大 #cf_span(class=[tex-font-style-underline], body=[Koyomity])。
输入的第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 500]) —— 花环的长度。
第二行包含 #cf_span[n] 个小写英文字母 #cf_span[s1s2... sn] 组成的字符串 —— 花环上纸片的初始颜色。
第三行包含一个正整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 200 000]) —— Nadeko 的计划数量。
接下来的 #cf_span[q] 行每行描述一个计划：第 #cf_span[i] 个计划包含一个整数 #cf_span[mi] (#cf_span[1 ≤ mi ≤ n]) —— 最多可重新染色的纸片数量，后跟一个空格，再跟一个小写英文字母 #cf_span[ci] —— Koyomi 可能最喜欢的颜色。
请输出 #cf_span[q] 行：对于每个工作计划，输出一行包含一个整数 —— 根据该计划重新染色花环后所能达到的最大 #cf_span(class=[tex-font-style-underline], body=[Koyomity])。
## Input
输入的第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1 500]) —— 花环的长度。
第二行包含 #cf_span[n] 个小写英文字母 #cf_span[s1s2... sn] 组成的字符串 —— 花环上纸片的初始颜色。
第三行包含一个正整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 200 000]) —— Nadeko 的计划数量。
接下来的 #cf_span[q] 行每行描述一个计划：第 #cf_span[i] 个计划包含一个整数 #cf_span[mi] (#cf_span[1 ≤ mi ≤ n]) —— 最多可重新染色的纸片数量，后跟一个空格，再跟一个小写英文字母 #cf_span[ci] —— Koyomi 可能最喜欢的颜色。
## Output
请输出 #cf_span[q] 行：对于每个工作计划，输出一行包含一个整数 —— 根据该计划重新染色花环后所能达到的最大 #cf_span(class=[tex-font-style-underline], body=[Koyomity])。
[samples]
## Note
在第一个样例中，有三个计划：
在第一个计划中，最多可以重新染色 #cf_span[1] 个纸片。将 "_y_" 染成 "_o_" 后得到 "_kooomi_"，其 #cf_span(class=[tex-font-style-underline], body=[Koyomity]) 为 #cf_span[3]，这是最优结果；
在第二个计划中，最多可以重新染色 #cf_span[4] 个纸片，得到 "_oooooo_"，其 #cf_span(class=[tex-font-style-underline], body=[Koyomity]) 为 #cf_span[6]；
在第三个计划中，最多可以重新染色 #cf_span[4] 个纸片，"_mmmmmi_" 和 "_kmmmmm_" 都能得到 #cf_span(class=[tex-font-style-underline], body=[Koyomity]) 为 #cf_span[5]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the garland.
Let $ s = (s_1, s_2, \dots, s_n) $ be a sequence of lowercase English letters representing initial colors.
Let $ q \in \mathbb{Z}^+ $ be the number of plans.
For each plan $ j \in \{1, \dots, q\} $, let $ m_j \in \mathbb{Z}^+ $ be the maximum number of pieces that can be repainted, and $ c_j $ be a lowercase English letter denoting Koyomi’s favorite color.
**Constraints**
1. $ 1 \leq n \leq 1500 $
2. $ 1 \leq q \leq 200000 $
3. For each plan $ j $: $ 1 \leq m_j \leq n $
**Objective**
For each plan $ j $, define a binary sequence $ b^{(j)} = (b_1^{(j)}, \dots, b_n^{(j)}) $ where:
$$
b_i^{(j)} =
\begin{cases}
0 & \text{if } s_i = c_j \\
1 & \text{otherwise}
\end{cases}
$$
Let $ L $ be the length of a contiguous subsegment $ [l, r] \subseteq [1, n] $.
The **Koyomity** of the garland under plan $ j $ is the maximum $ L $ such that:
$$
\sum_{i=l}^{r} b_i^{(j)} \leq m_j
$$
Compute this maximum $ L $ for each plan $ j $.
API Response (JSON)
{
"problem": {
"name": "C. An impassioned circulation of affection",
"description": {
"content": "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! Stil",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF814C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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!\n\nStil...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Nadeko 的生日快到了！她在为派对装饰房间时，将一条由 Dianthus 形状纸片组成的长花环放在了墙上的显眼位置。哥哥 Koyomi 一定会喜欢！\n\n但 Nadeko 对花环仍不满意，决定再打磨一次。这条花环有 #cf_span[n] 个纸片，从左到右编号为 #cf_span[1] 到 #cf_span[n]，第 #cf_span[i] 个纸片的颜色为 #cf_span[si]，用一个小写英...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the garland. \nLet $ s = (s_1, s_2, \\dots, s_n) $ be a sequence of lowercase English letters representing initial colors. \nLet $ q \\in \\m...",
"is_translate": false,
"language": "Formal"
}
]
}