29228번 - Лучшие друзья Беллы 스페셜 저지다국어

문제

Скоро день рождения Беллы, и Эдвард собирается преподнести ей в подарок роскошное ожерелье из драгоценных камней. Ожерелье состоит из драгоценных камней нескольких типов. Но вот незадача: Эдвард не знает предпочтения Беллы и может только догадываться, какие камни ей нравятся.

Ювелир уже изготовил одно большое ожерелье, но он может вырезать из него некоторое количество подряд идущих камней и сделать из него новое ожерелье. Однако, есть еще одна проблема: Белле нравятся только те ожерелья, в которых количества камней каждого типа, которые ей нравятся, одинаковы. Количество тех камней, которые ей не нравятся, ей безразлично.

Драгоценные камни обозначаются строчными буквами английского алфавита. Вампиры крайне суеверны, и, в частности, камни, которым соответствуют гласные буквы, считаются приносящими беду, поэтому их в изначальном ожерелье нет. Согласными буквами являются все буквы английского алфавита, кроме букв A, E, I, O, U.

Эдвард пришел в ювелирный магазин, и у него есть $q$ предположений по поводу предпочтений Беллы. Для каждого из этих предположений Эдвард хочет узнать, какова максимально возможная длина ожерелья, которую ювелир может получить из уже изготовленного. Новое ожерелье должно состоять из каких-то подряд идущих камней из уже готового ожерелья. Помогите ему!

입력

В первой строке находится целое число $n$ (1ドル \le n \le 5000$) --- длина уже изготовленного ожерелья. Во второй строке находятся $n$ строчных согласных букв английского алфавита --- описание этого ожерелья. В следующей строке находится целое число $q$ --- число предположений Эдварда (1ドル \le q \le 10^5$). В каждой из следующих $q$ строк находится описание очередного предположения: число $k$ (1ドル \le k \le 21$) --- количество камней, которые, как кажется Эдварду, нравятся Белле. Через пробел идет строка из $k$ строчных согласных букв английского алфавита ---перечисление камней, которые могут нравиться Белле. Все символы в этой строке различны.

출력

Для каждого предположения Эдварда выведите ответ в отдельной строке. Ответом являются два числа $l$ и $r$ (1ドル \le l \le r \le n$), означающие, что Эдварду надо выбрать камни c $l$ по $r$ включительно. Количества букв, перечисленных Эдвардом в соответствующем предположении, должны совпадать, а длина должна быть максимальной. Если таких $l$ и $r$ не существует, выведите единственное число -1.

제한

힌트