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

你想要打印这个字典。然而，打印系统存在一个错误，列表中的所有单词被紧挨着打印出来，单词之间没有任何分隔符。现在，你得到一个字符串 $S$，它是字典中所有单词按列表顺序连接而成的。

你的任务是通过将 $S$ 拆分为一个或多个单词来重构字典。注意，重构后的字典必须由按字母顺序排列的不同单词组成。此外，你希望最大化字典中单词的数量。如果存在多个单词数量最多的字典，你可以选择其中任意一个。

输入格式

一行，包含一个字符串 $S$ ($1 \le |S| \le 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