eolymp
bolt
Try our new interface for solving problems
Məsələlər

Дана строкаТМ

Дана строкаТМ

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

  • рассмотреть данную строку^TM s

  • выбрать некоторую строку t

  • заменить некоторые непересекающиеся вхождения t в s на переменнуюA, обозначаемую (что удивительно) заглавной латинской буквой 'A', получив строку g.

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
aaabaaa
Çıxış verilənləri #1
aaa
AbA