28547번 - Зашифрованное сообщение 스페셜 저지다국어

문제

Во время расследования Бенуа Бланк обнаружил подозрительную записку, оставленную кем-то на месте преступления. Текст в записке $t$ на первый взгляд не имел никакого смысла, но после долгого анализа записки Бланк пришел к выводу, что сообщение осмысленно, но зашифровано.

Шифр, использованный в записке, довольно нестандартный. Каждое слово было зашифровано отдельно, после чего все слова были склеены вместе, чтобы не было понятно, где какое слово начинается и заканчивается. Поэтому первым делом детектив решил восстановить, где находятся границы слов, а после уже взяться за их расшифровку.

Известно, что текст на записке был получен следующим образом: набор зашифрованных слов $w_1, w_2, \ldots, w_n$ был продублирован в развернутом виде, после чего выписан без пробелов. Иными словами, $t = (w_1 + \ldots + w_n) + (w_n + \ldots + w_1),ドル где знак '+' обозначает конкатенацию.

Помогите Бенуа Бланку восстановить исходный набор зашифрованных слов. Поскольку Бланк считает, что сообщение содержало много слов, из всех способов разбить $t$ на слова в соответствии с условием выберите тот, в котором количество слов максимально.

입력

Во вводе дана единственная строка $t$ из маленьких латинских букв --- зашифрованный текст (1ドル \leqslant |t| \leqslant 10^6$).

출력

В первой строке выведите целое число $n$ --- максимально возможное количество слов в зашифрованном тексте. В следующих $n$ строках перечислите сами слова по одному на каждой строке.

Если ответов с максимальным $n$ несколько, выведите любой из них.

Гарантируется, что ответ существует.

제한

힌트