C. Пылкий поток любви
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

День рождения Надеко приближается! Так как она украсила комнату для вечеринки, длинная гирлянда из бумажных гвоздик была повешена на видную часть стены. Койому, брату Надеко, она понравится!

Надеке все еще не нравится гирлянда, поэтому она решила ее снова улучшить. Гирлянда состоит из n частей, пронумерованных слева направо от 1 до n, и i-я из этих частей имеет цвет si, обозначенный строчной латинской буквой. Надеко перекрасит не более m частей в любой цвет (по-прежнему обозначенный строчной латинской буквой). После этого, она найдет все подотрезки, состоящие только из частей цвета c — любимого цвета Койоми — и будет называть длину самого большого такого подотрезка койомностью гирлянды.

Пусть, например, гирлянда имеет цвета «kooomo», а любимый цвет Койоми — «o». Среди всех подотрезков, содержащих только цвет «o», самым длинным является «ooo», его длина равна 3. Поэтому койомность этой гирлянды равна 3.

Проблема в том, что Надеко не уверена в любимом цвете Койоми, поэтому она постоянно меняет свои планы на предстоящую работу. У нее есть q планов, каждый определяется парой из числа mi и строчной буквы ci, значения которых были объяснены раньше. Вам предстоит найти максимальную койомность, достижимую после изменения гирлянды в соответствии с каждым из планов.

Входные данные

Первая строка содержит одно положительное целое число n (1 ≤ n ≤ 1 500) — длину гирлянды.

Вторая строка содержит n строчных латинских букв s1s2... sn как строку — начальные цвета частей гирлянды.

Третья строка содержит целое положительное число q (1 ≤ q ≤ 200 000) — количество планов у Надеко.

Каждая из следующих q строк описывает один план: строка i из них содержит целое число mi (1 ≤ mi ≤ n) — максимальное число частей, которое можно перекрасить, и затем строчную латинскую букву ci — возможный любимый цвет Койоми.

Выходные данные

Выведите q строк: для каждого плана выведите одно целое число на отдельной строке — максимально возможную койомность, достижимую после изменения гирлянды в соответствии с этим планом.

Примеры
Входные данные
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
Примечание

В первом примере есть три плана:

  • В первом плане можно перекрасить не более чем 1 часть. Перекрасив часть цвета «y» в цвет «o», получим «kooomi», койомность которой равна 3 — максимально возможной;
  • Во втором плане можно перекрасить не более чем 4 части, получив гирлянду «oooooo», койомность которой равна 6;
  • В третьем случае можно перекрасить не более 4 частей, два способа «mmmmmi» и «kmmmmm» являются оптимальными с койомностью, равной 5.