Строка \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 В первой строке выведите количество псевдо-шаблонов заданной строки. Во второй строке выведите кратчайший из псевдо-шаблонов. Если кратчайших псевдо-шаблонов несколько, выведите лексикографически минимальный из них.