D. Частота строки
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$. Требуется ответить на $$$n$$$ запросов. $$$i$$$-й запрос состоит из целого числа $$$k_i$$$ и строки $$$m_i$$$, ответом является минимальная длина строки $$$t$$$ такой, что $$$t$$$ является подстрокой $$$s$$$ и строка $$$m_i$$$ входит в $$$t$$$ как подстрока не менее $$$k_i$$$ раз.

Подстрокой строки называется любая последовательность подряд идущих символов в этой строке.

Гарантируется, что для любых двух запросов строки $$$m_i$$$ из этих запросов различны.

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

В первой строке содержится строка $$$s$$$ $$$(1 \leq \left | s \right | \leq 10^{5})$$$.

Во второй строке содержится целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

В каждой из следующих $$$n$$$ строк содержатся целое число $$$k_i$$$ $$$(1 \leq k_i \leq |s|)$$$ и непустая строка $$$m_i$$$ — параметры запроса с номером $$$i$$$.

Все строки во вводе состоят только из строчных букв латинского алфавита. Суммарная длина всех строк во вводе не превосходит $$$10^5$$$. Все $$$m_i$$$ различны.

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

Для каждого запроса выведите ответ на него в отдельной строке.

Если строка $$$m_{i}$$$ встречается в $$$s$$$ менее $$$k_{i}$$$ раз, выведите -1.

Примеры
Входные данные
aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa
Выходные данные
3
4
4
-1
5
Входные данные
abbb
7
4 b
1 ab
3 bb
1 abb
2 bbb
1 a
2 abbb
Выходные данные
-1
2
-1
3
-1
1
-1