Заикающиеся пришельцы
Доктор Элли Эрроуэй установила контакт с внеземной цивилизацией. Однако все попытки расшифровать их сообщения пока не увенчались успехом, поскольку они столкнулись с расой заикающихся пришельцев! Её команда выяснила, что в каждом достаточно длинном сообщении самые важные слова повторяются определённое количество раз в виде последовательности последовательных символов, даже если они находятся в середине других слов. Более того, иногда они используют сокращения в неясной манере. Например, если им нужно сказать "bab" дважды, они могут просто отправить сообщение "babab", которое было сокращено, потому что вторая "b" первого слова может быть использована как первая "b" второго.
Таким образом, сообщение может содержать перекрывающиеся повторения одних и тех же слов снова и снова. В результате Элли обращается к вам, С.Р. Хэддену, за помощью в определении сути сообщения.
Дано целое число m и строка s, представляющая сообщение. Ваша задача — найти самую длинную подстроку из s, которая появляется как минимум m раз. Например, в сообщении baaaababababbababbab слово длиной 5 babab содержится 3 раза, а именно на позициях 5, 7 и 12 (где индексы начинаются с нуля). Ни одна подстрока, появляющаяся 3 или более раз, не длиннее (см. первый пример из входных данных). С другой стороны, ни одна подстрока не появляется 11 раз или более (см. пример 2).
Если есть несколько решений, предпочтение отдаётся подстроке с самым правым вхождением (см. пример 3).
Входные данные
Вход содержит несколько тестовых случаев. Каждый тестовый случай состоит из строки с целым числом m (m ≥ 1), минимальным количеством повторений, за которым следует строка, содержащая строку s длиной от m до 40 000, включительно. Все символы в s — это строчные буквы от “a” до “z”. Последний тестовый случай обозначается m = 0 и не должен обрабатываться.
Выходные данные
Выведите одну строку для каждого тестового случая. Если решения нет, выведите "none"; в противном случае выведите два целых числа в строке, разделённых пробелом. Первое число обозначает максимальную длину подстроки, появляющейся как минимум m раз; второе число указывает на самое правое начальное положение этой подстроки.