ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1635. Mnemonics and Palindromes

Time limit: 1.0 second
Memory limit: 64 MB
The student Vasechkin was terribly unlucky at his oral examination. Of 42 examination questions, he didn't prepare only the last one, and he was asked exactly that question. Vasechkin was sitting in front of the professor and couldn't say anything. But the professor was in good mood and gave Vasechkin one last chance to pass the exam. He asked the poor student to name the subject in which the exam was being held. Unfortunately, Vasechkin couldn't recall the name, though he remembered that in that name there were such words as safety, programs, devices, and, possibly, informatics…
To get ready for the reexamination, Vasechkin decided to learn the name of the subject. To better remember that long string, he decided to decompose it into palindromes and learn each of the palindromes separately. Of course, the number of palindromes in the decomposition had to be as small as possible.

Input

In the first line there is the name of the subject in which Vasechkin was examined. This is a nonempty line consisting of lowercase English letters. The length of the line is at most 4000 symbols.

Output

In the first line output the minimal number of palindromes to which the name of the subject can be decomposed. In the second line output palindromes from the optimal decomposition separated by a space. If several answers are possible, output any of them.

Samples

inputoutput
pasoib
6
p a s o i b
zzzqxx
3
zzz q xx
wasitacatisaw
1
wasitacatisaw
Problem Author: Igor Chevdar
Problem Source: XIII Open USU Championship