1448 - 分割回文串

通过次数

14

提交次数

17

Time Limit : 1 秒
Memory Limit : 128 MB

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文串 。返回 s 所有可能的分割方案。

Input

Output

Examples

Input

aab

Output

a a b
aa b

Input

a

Output

a

Hint

1 <= s.length <= 16 , s 仅由小写英文字母组成