1954. Five Palindromes @ Timus Online Judge

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 ≤ 10⁵).

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

input	output
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