Студенту Васечкину чудовищно не повезло на экзамене. Из 42 билетов он не подготовил только последний, и ему достался именно этот билет. Теперь же Васечкин сидел перед преподавателем и не мог ответить ни на один вопрос. Однако преподаватель пребывал в весьма добром расположении духа и решил дать Васечкину последний шанс на тройку. Он спросил его, как называется предмет, который Васечкин сейчас сдаёт. К несчастью, Васечкин не смог вспомнить точную аббревиатуру, припоминая лишь, что в названии фигурировала чья-то безопасность, какие-то программы и аппараты и, кажется, информатика…

К пересдаче Васечкин решил выучить название предмета. Чтобы лучше запомнить эту длинную строку, он решил разбить её на палиндромы и запомнить каждый из них по отдельности. Конечно, количество палиндромов в разбиении должно быть минимально возможным.

В первой строке записано название предмета, который сдавал Васечкин, — непустая строка, содержащая только маленькие латинские буквы. Длина строки не превосходит 4000 символов.

В первой строке выведите минимальное количество палиндромов, на которое можно разбить название предмета. Во второй строке через пробел выведите палиндромы из оптимального разбиения. Если возможных ответов несколько, выведите любой.