Maximum Palindromic Partition

Given a string s consisting of only lowercase letters, partition it into contiguous blocks such that the sequence of blocks forms a palindrome. In other words, if the partition is X₁, X₂, ..., X_k, it must hold that \[ X_i = X_{k-i+1} \quad \text{for } 1 \le i \le k. \]

Your task is to choose a valid partition that maximizes the number of blocks. If there are multiple solutions with the maximum number of blocks, output any one of them.

Note: The blocks must be contiguous substrings of the original string.

Example:

Input: abcab
One possible output: ab c ab
Explanation: The partition ["ab", "c", "ab"] forms a palindromic sequence since the first and last blocks are identical. Although the whole string "abcab" is also a valid partition (as a single block), it does not maximize the number of blocks.

inputFormat

The input consists of a single line containing the string s (1 ≤ |s| ≤ 10⁵), which is composed only of lowercase letters.

outputFormat

Output the blocks of your partition separated by a single space. The output partition must form a palindrome sequence and use the maximum possible number of blocks.

sample

abcab

ab c ab