Псевдо-шаблон
Рядок t називається шаблоном рядка s, якщо всі входження рядка t у рядок s разом покривають весь рядок s (тобто для кожної позиції в рядку s існує хоча б одне входження рядка t, яке накриває цю позицію). Наприклад, рядок aba є шаблоном для ababaaba. Рядок t називається псевдо-шаблоном рядка s, якщо він одночасно:
є підрядком s,
є шаблоном деякого рядка, що містить s.
Наприклад, рядок abaa є псевдо-шаблоном рядка aabaabaab, оскільки він є його підрядком і також є шаблоном рядка abaabaabaabaa.
Вам задано рядок s. Знайдіть кількість його псевдо-шаблонів і найкоротший з них.
Вхідні дані
Вхідні дані складаються з одного рядка довжиною від 1 до 2 10^5, що складається з малих літер латинського алфавіту.
Вихідні дані
У першому рядку виведіть кількість псевдо-шаблонів заданого рядка. У другому рядку виведіть найкоротший з псевдо-шаблонів. Якщо найкоротших псевдо-шаблонів декілька, виведіть лексикографічно мінімальний з них.