eolymp
bolt
Try our new interface for solving problems
Problems

Five Palindromes

Five Palindromes

Time limit 6 seconds
Memory limit 64 MiB

Your task is to divide a string into five non-empty palindromes.

Input data

Oone string consisting of n (5 n 10^5) lowercase English letters.

Output data

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.

Examples

Input example #1
aaabbcdcaa
Output example #1
YES
a
aa
bb
cdc
aa
Author M.Rubinchik, K.Borozdin
Source 2013 Petrozavodsk, Winter, Ural FU contest, Kontur Cup, Problem D