Problems
Псевдо-шаблон
Псевдо-шаблон
Строка \textbf{t} называется шаблоном строки \textbf{s}, если объединение всех вхождений строки \textbf{t} в строку \textbf{s} покрывает всю строку \textbf{s} (т.е. для любой позиции строки \textbf{s} найдется как минимум одно вхождение строки \textbf{t}, накрывающее эту позицию). Например, строка \textbf{aba} является шаблоном для \textbf{ababaaba}. Строка \textbf{t} называется псевдо-шаблоном строки \textbf{s}, если она одновременно:
\begin{itemize}
\item является подстрокой \textbf{s},
\item является шаблоном некоторой строки, содержащей \textbf{s}.
\end{itemize}
К примеру, строка \textbf{abaa} является псевдо-шаблоном строки \textbf{aabaabaab}, потому что входит в нее как подстрока и является шаблоном строки \textbf{abaabaabaabaa}.
Вам задана строка \textbf{s}. Найдите количество её псевдо-шаблонов и самый короткий из них.
\InputFile
Входные данные состоят из единственной строки длиной от \textbf{1} до \textbf{2·10^5}, состоящей из строчных букв латинского алфавита.
\OutputFile
В первой строке выведите количество псевдо-шаблонов заданной строки. Во второй строке выведите кратчайший из псевдо-шаблонов. Если кратчайших псевдо-шаблонов несколько, выведите лексикографически минимальный из них.
Input example #1
aabaabaab
Output example #1
18 aab