你有一本字典,它是按字母顺序排序的不同单词的列表。每个单词均由大写英文字母组成。
您想要打印这本词典。但是,打印系统存在一个错误,列表中的所有单词都彼此相邻打印,单词之间没有任何分隔符。现在,您最终得到了一个字符串 $$$S$$$,它是字典中所有单词按列出顺序串联而成的。
您的任务是将 $$$S$$$ 拆分为一个或多个单词来重建字典。请注意,重建的字典必须由按字母顺序排序的不同单词组成。此外,您希望最大化词典中的单词数量。如果有多个可能的词典具有最大字数,您可以选择其中任何一个。
输入
由字符串 $$$S$$$ ($$$1 \leq |S| \leq 5000)$$$ 组成的单行。字符串 $$$S$$$ 仅由大写英文字母组成。
输出
首先,在单行中输出一个整数,表示重构词典中单词的最大数量。将此数字表示为 $$$n$$$。
然后,输出 $$$n$$$ 行,每行包含一个代表单词的字符串。单词必须不同,并且列表必须按字母顺序排序。按列出的顺序串联的单词必须等于 $$$S$$$。
如果存在多个可能的具有最大字数的词典,则输出其中任何一个。
示例
输入 #1
ABACUS
输出 #1
4 A BA C US
输入 #2
AAAAAA
输出 #2
3 A AA AAA
输入 #3
EDCBA
输出 #3
1 EDCBA