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

1954. Five Palindromes

Time limit: 1.0 second
Memory limit: 64 MB
Your task is to divide a string into five non-empty palindromes.

Input

The input contains one string consisting of n lowercase English letters (5 ≤ n ≤ 105).

Output

Output “NO” if such division is impossible. Otherwise, output “YES” on the first line, and the next five lines should contain one palindrome each, which, if concatenated in this order, form the given string.

Samples

inputoutput
aaabbcdcaa
YES
aa
a
bb
cdc
aa
spaaaaaaarta
NO
abacdcxyxzpz
NO
Problem Author: Mikhail Rubinchik (prepared by Kirill Borozdin)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013