Заїкуваті прибульці
Доктор Еллі Ерровей встановила контакт із позаземною цивілізацією. Проте всі спроби розшифрувати їхні повідомлення поки що не увінчалися успіхом, оскільки вони зіткнулися з расою заїкуватих прибульців! Її команда з'ясувала, що в кожному достатньо довгому повідомленні найважливіші слова повторюються певну кількість разів у вигляді послідовності підрядків, навіть якщо вони знаходяться всередині інших слів. Більше того, іноді вони використовують скорочення в неясній манері. Наприклад, якщо їм потрібно сказати "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 разів; друге число вказує на найбільш праве початкове положення цього підрядка.