Задача H. (20081225) Палиндромное кодирование ≡

Условие

В одной секретной лаборатории разработали новый сверхсекретный способ архивации данных. Этот метод настолько уникален, что позволяет все данные сжимать примерно в 2 раза. Заключается он в следующем. Шифруемый файл представляется в виде последовательности из нулей и единиц. Потом из этой последовательности выбирается непустая подпоследовательность, которая является палиндромом. Затем из оставшейся части выбирается непустая последовательность, которая является палиндромом и т.д. Таким образом, из исходной последовательности остаётся только несколько палиндромов. Но ведь от палиндромов теперь можно хранить только одну половину!

Сразу видно, насколько хорош этот метод. Однако есть и небольшие трудности — чем на большее число палиндромов приходится разбивать строку при архивации, тем сложнее потом разархивировать. Поэтому требуется программа, которая разобьёт последовательность на минимальное количество палиндромов.

Однако комиссия по проверке не согласилась принимать такой алгоритм, сказав, что программа архивации работает нестабильно и по-разному архивирует один и тот же файл. Для унификации был придуман следующий метод: изо всех способов разбить на минимальное число палиндромов выбирается такой, в котором первый палиндром лексикографически наименьший. Изо всех таких — тот, в котором второй наименьший. И так далее.

Ваша задача — написать программу для архивации данных описанным выше способом.

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

В первой и единственной строке входного файла содержится непустая строка из нулей и единиц длиной не более 3 000 000 символов.

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

В первой строке выведите число N — минимальное число палиндромов. В следующих N строках выведите сами палиндромы, по одному на строке.

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

1001

1
1001