Дано рядокТМ
Співробітник широко відомого НДІІДС Василь виявив, нарешті, на своєму робочому місці комп'ютер. Не будучи занадто досвідченим користувачем, він не став використовувати усі можливості цього загадкового агрегату. Проте зі шкільного курсу Василь пам'ятає, що програмісти користються таким поняттям, як змінні. Як ними користуватись, він не дуже пам'ятає, тому вирішив застосувати одну наслтупним чином:
розглянути заданий рядок^TM s
вибрати деякий рядок t
замінити деякі входження, що не перетинаються, t в s на змінну A, яка позначається (що дивно) великою латинською літерою 'A', отримавши рядок g.
При цьому метою Василя є мінімізація загальної кількості символів, тобто |t| + |g|.
Вхідні дані
У першому і єдиному рядку міститься заданий рядок^TM s (1 ≤ |s| ≤ 10000). Він кладається з маленьких літер латинського алфавіту.
Вихідні дані
Виведіть оптимальний набір: у першому рядку t, а у другому - g.