1653: 回文子串

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

回文串是正着读和反着读都一样的字符串。给定一个字符串 s,请将 s 分割成一些子串,使每个子串都是回文串;返回s 所有可能的分割方案。

Input

输入字符串s。(1<=|s|<=200,s 仅由小写英文字母组成)

Output

输出符合题意的分割方案,每行的分割回文子串,用空格分割。

Sample Input Copy

aab

Sample Output Copy

a a b
aa b

HINT

【样例输入2】

abc

【样例输出2】

a b c


【样例输入3】

a

【样例输出3】

a