novel

Адриан е доволен, защото е заедно с Лаура. Той даже е написал роман за любовта. Но днес Лаура му развали настроението. След като прочела романа, тя му казала, че има чувството, че някои фрагменти от романа се повтарят. Даже имало изречения, които се повтаряли по няколко пъти, но Лаура не можела да си спомни точно. Адриан решил да провери като започне да търси кои последователности от знаци в текста се повтарят и от кои позиции.

Задача

Намерете най-дългата последователност, която се повтаря поне K пъти в текста на романа.

Вход

Файлът novel.in съдържа в първия си ред цялото положително число K. Следващите редове съдържат текста на романа.  

Изход

Файлът novel.out трябва да съдържа в първия си ред две цели положителни числа L и N, разделени с интервал. Те трябва да са съответно равни на максималната дължина на последователността от знаци, която се повтаря поне K пъти и на точния брой повторения.
На втория ред, разделени с интервали, трябва да се изведат числата
I0 I1 ... IN, определящи началните позиции на всяка една от N + 1 идентични последователности с дължина L.
Започвайки от третия ред, трябва да са изведени максималната по дължина последователност от знаци, повтаряща се поне K пъти. Не отпечатвайте знак за нов ред на края на последователността.

Ограничения и пояснения

Пример

novel.in

novel.out

Обяснение

1
Now I feel, like I've been
to heaven and back 100 times

Every time I look in her eyes
Yes, I feel, like I've been
to heaven and back 100 times
I look deep in her light brown eyes
and I loved her
Why, why, oh, me
Why couldn't she see
that I loved her so much
God, I love to look in her eyes...
And I feel, like I've been
to heaven and back 100 times

Yes, I feel...

53 2
3 90 296
 I feel, like I've been
to heaven and back 100 times

53 е максималният брой на знаците на последователността, която се повтаря поне веднъж. Тя се среща в текста на 3 места, следователно се повтаря 2 пъти. Тази последователност е:


 I feel, like I've been
to heaven and back 100 times


3, 90 и 296 са позициите на първия знак от последователността стрямо позицията на първия знак 'N' от текста. Първият знак на намерената последователност е ' ', а последният е newline.

Време за работа на програмата: 1 секунда за тест.
Ограничение за памет: 2
MB, от които 1 MB за стек.

prof. Constantin Galatan
C.N. "Liviu Rebreanu" Bistriţa
tucu_galatan@yahoo.com

Превод на български: Емил Келеведжиев