Recursive palindrome assembly from substrings

Rust Hard functions

Task «Recursive palindrome assembly from substrings»

Given a string S consisting of lowercase Latin letters. It is necessary to recursively (using a function) split the original string into the minimum number of palindromic substrings (each substring must be a palindrome) and output them separated by a space. If splitting is impossible (for example, the string is empty), output "NO". Constraints: the length of S is from 1 to 1000 characters. It is guaranteed that an answer exists.

Input Format

One string S (1 ≤ |S| ≤ 1000).

Output Format

A string containing palindrome substrings separated by a space. If the input string is empty, output "NO".

Examples

Example 1

INPUT

racecar

OUTPUT

racecar

Example 2

INPUT

aab

OUTPUT

aa b

main.rs