Дано рядокТМ#1769
Василь, співробітник відомого Європейського інституту передових досліджень, нарешті знайшов комп'ютер на своїй роботі. Оскільки він не дуже досвідчений з комп'ютерами, то не використовував усі можливості цього загадкового пристрою. Проте зі шкільних часів Василь пам'ятає, що програмісти використовують так звані змінні. Точно не пригадавши, як саме ними користуватися, він вирішив застосувати одну з них так:
Розглянути заданий рядок s.
Обрати рядок t.
Замінити деякі неперекривні входження t у s на змінну A, що (несподівано) позначається великою латинською літерою 'A', отримавши рядок g.
Мета Василя — мінімізувати загальну кількість символів, тобто |\textbf{t}| + |\textbf{g}|.
Вхідні дані складаються з одного рядка, що містить рядок s (1 \leq |\textbf{s}| \leq 10000). Рядок складається з малих латинських літер.
Виведіть оптимальну пару: спочатку рядок t у першому рядку, а потім рядок g у другому рядку.
Приклад 1