说明

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

你想打印这本词典。然而，打印系统存在一个错误，导致列表中的所有单词在打印时彼此紧挨着，单词之间没有任何分隔符。最终，你得到了一个字符串 $S$，它是词典中所有单词按列表顺序拼接而成的结果。

你的任务是通过将 $S$ 分割成一个或多个单词来重建这本词典。注意，重建后的词典必须由互不相同的单词组成，并且按字典序排序。此外，你希望最大化词典中的单词数量。如果有多个单词数量最多的可能词典，你可以选择其中任意一个。

输入格式

一行，包含一个字符串 $S$（$1 \leq |S| \leq 5000$）。字符串 $S$ 仅由大写英文字母组成。

输出格式

首先，在一行中输出一个整数，表示重建词典中单词的最大数量。记这个数为 $n$。

然后，输出 $n$ 行，每行包含一个字符串，表示一个单词。这些单词必须互不相同，并且列表必须按字典序排序。这些单词按列表顺序拼接后必须等于 $S$。

如果有多个单词数量最多的可能词典，输出其中任意一个。

ABACUS

4
A
BA
C
US

AAAAAA

3
A
AA
AAA

EDCBA

1
EDCBA

提示

翻译由 DeepSeek V3.2 完成