说明

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

按  从短到长 顺序输出。

回文串 是正着读和反着读都一样的字符串。

输入格式

一行字符串 s 。

输出格式

所有可能的分割方案，每个方案一行，字符串之间单个空格隔开

按照从短到长的顺序输出

样例

aab

a a b
aa b

提示

数据范围：

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