Сотрудник небезызвестного НИИИДС Василий обнаружил, наконец, на своём рабочем месте компьютер. Не будучи слишком опытным пользователем, он не стал использовать все возможности этого загадочного агрегата. Однако из школьного курса Василий помнит, что программисты пользуются таким понятием, как \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}.