Дана строка \(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
1500 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач