Задача K. Дана строка

Автор:Жюри летних сборов 2009   Ограничение времени:2 сек
Входной файл:string.in   Ограничение памяти:256 Мб
Выходной файл:string.out  
Максимальный балл:100  

Условие

Сотрудник небезызвестного НИИИДС Василий обнаружил, наконец, на своём рабочем месте компьютер. Не будучи слишком опытным пользователем, он не стал использовать все возможности этого загадочного агрегата. Однако из школьного курса Василий помнит, что программисты пользуются таким понятием, как \emph{переменные}. Как ими пользоваться, он не очень помнит, поэтому решил применить одну следующим образом:

При этом целью Василия является минимизация общего количества символов, то есть |t| + |g|.

Формат входного файла

В первой и единственной строке содержится данная строка s (1 ≤ |s| ≤ 10 000). Она состоит из строчных букв латинского алфавита.

Формат выходного файла

Выведите оптимальный набор: в первой строке t, а во второй — g.

Примеры тестов

Входной файл (string.in) Выходной файл (string.out)
1
aaabaaa
aaa
AbA

0.035s 0.009s 15