H. 缺失的分隔符
每个测试点时间限制：$1$ 秒
每个测试点内存限制：$1024$ 兆字节

你有一个字典，它是一个按字母顺序排序的互不相同的单词列表。每个单词由大写英文字母组成。

你想打印这个字典。然而，打印系统有一个错误，列表中的所有单词都连在一起打印，单词之间没有任何分隔符。现在，你得到了一个字符串 $S$，它是按列表顺序拼接所有单词后得到的。

你的任务是通过将 $S$ 分割成一个或多个单词来重建字典。注意，重建的字典必须包含互不相同的单词，并且这些单词按字母顺序排序。此外，你要让字典中的单词数量尽可能多。如果有多个字典能实现最多的单词数，你可以输出任意一个。

输入
一行，包含一个字符串 $S$（$1 \le |S| \le 5000$）。字符串 $S$ 只包含大写英文字母。

输出
第一行输出一个整数，表示重建字典中单词的最大数量，记作 $n$。
接下来 $n$ 行，每行输出一个字符串，表示一个单词。这些单词必须互不相同，并且列表按字母顺序排列。按列表顺序将这些单词拼接起来必须等于 $S$。
如果有多种方案能达到最大单词数，输出任意一种。

样例

输入

ABACUS

输出

4
A
BA
C
US

输入

AAAAAA

输出

3
A
AA
AAA

输入

EDCBA

输出

1
EDCBA