해결한 사람
0
명
정답률
0.00
%
시간 제한
2000
ms
메모리 제한
245
MB
Nadeko의 생일이 다가오고 있다! Nadeko가 파티를 위해 방을 꾸미면서, 패랭이꽃 모양의 종이 조각들로 이루어진 긴 화환이 벽의 눈에 잘 띄는 곳에 놓였다. Brother Koyomi은 이를 좋아할 것이다!
여전히 화환에 만족하지 못한 Nadeko는 화환을 다시 다듬기로 했다. 화환에는 왼쪽에서 오른쪽으로 1부터 n까지 번호가 매겨진 n개의 조각이 있으며, i-th번째 조각의 색은 소문자 영문자로 나타내는 si이다. Nadeko는 조각 중 최대 m개를 각각 임의의 새로운 색으로 다시 칠한다. 새로운 색 역시 소문자 영문자로 나타낸다. 이 작업 후, Nadeko는 Brother Koyomi's이 가장 좋아하는 색인 c 하나로만 이루어진 조각들을 포함하는 화환의 모든 부분 구간을 찾고, 그중 가장 긴 것의 길이를 화환의 Koyomity로 삼는다.
예를 들어 화환이 "kooomo"로 표현되고, Brother Koyomi's이 가장 좋아하는 색이 "o"라고 하자. "o"만으로 이루어진 조각들을 포함하는 모든 부분 구간 중 "ooo"가 길이 3으로 가장 길다. 이 화환의 Thus the Koyomity는 3이다.
하지만 Nadeko는 Brother Koyomi's이 가장 좋아하는 색을 확신하지 못하고, 얼마나 많은 작업을 할지에 대해서도 생각이 흔들려 문제가 생긴다. Nadeko에게는 이에 관한 q개의 계획이 있으며, 각 계획은 정수 mi와 소문자 ci의 쌍으로 나타낼 수 있다. 각각의 의미는 위에서 설명한 것과 같다. 각 계획에 따라 화환을 다시 칠한 뒤 달성할 수 있는 최대 Koyomity를 구해야 한다.
입력의 첫 번째 줄에는 화환의 길이인 양의 정수 n (1 ≤ n ≤ 1 500)가 주어진다.
두 번째 줄에는 화환에 있는 종이 조각들의 초기 색을 나타내는 n개의 소문자 영문자 s1s2... sn이 문자열로 주어진다.
세 번째 줄에는 Nadeko가 가진 계획의 수인 양의 정수 q (1 ≤ q ≤ 200 000)가 주어진다.
다음 q개의 줄에는 각각 하나의 계획이 주어진다. 그중 i-th번째 줄에는 다시 칠할 조각 수의 최댓값인 정수 mi (1 ≤ mi ≤ n)가 주어지고, 이어서 공백 하나와 Koyomi가 가장 좋아할 가능성이 있는 색인 소문자 ci가 주어진다.
q개의 줄을 출력한다. 각 작업 계획에 대해, 그 계획에 따라 화환을 다시 칠한 후 달성할 수 있는 가장 큰 Koyomity를 나타내는 정수를 한 줄에 출력한다.
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
6
koyomi
3
1 o
4 o
4 m
3
6
5
10
aaaaaaaaaa
2
10 b
10 z
10
10
첫 번째 예제에는 세 가지 계획이 있다: