Зашифрованное сообщение

Во время расследования Бенуа Бланк обнаружил подозрительную записку, оставленную кем-то на месте преступления. Текст в записке $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$ несколько, выведите любой из них.

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