Псевдо-шаблон
Строка t называется шаблоном строки s, если объединение всех вхождений строки t в строку s покрывает всю строку s (т.е. для любой позиции строки s найдется как минимум одно вхождение строки t, накрывающее эту позицию). Например, строка aba является шаблоном для ababaaba. Строка t называется псевдо-шаблоном строки s, если она одновременно:
является подстрокой s,
является шаблоном некоторой строки, содержащей s.
К примеру, строка abaa является псевдо-шаблоном строки aabaabaab, потому что входит в нее как подстрока и является шаблоном строки abaabaabaabaa.
Вам задана строка s. Найдите количество её псевдо-шаблонов и самый короткий из них.
Входные данные
Входные данные состоят из единственной строки длиной от 1 до 2·10^5, состоящей из строчных букв латинского алфавита.
Выходные данные
В первой строке выведите количество псевдо-шаблонов заданной строки. Во второй строке выведите кратчайший из псевдо-шаблонов. Если кратчайших псевдо-шаблонов несколько, выведите лексикографически минимальный из них.