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