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.

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.

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.