You have a dictionary, which is a list of distinct words sorted in alphabetical order. Each word consists of uppercase English letters.
You want to print this dictionary. However, there is a bug with the printing system, and all words in the list are printed next to each other without any separators between words. Now, you ended up with a string that is a concatenation of all the words in the dictionary in the listed order.
Your task is to reconstruct the dictionary by splitting into one or more words. Note that the reconstructed dictionary must consist of distinct words sorted in alphabetical order. Furthermore, you want to maximize the number of words in the dictionary. If there are several possible dictionaries with the maximum number of words, you can choose any of them.
输入格式
A single line consisting of a string ( . String consists of only uppercase English letters.
输出格式
First, output an integer in a single line representing the maximum number of the words in the reconstructed dictionary. Denote this number as .
Then, output lines, each containing a single string representing the word. The words must be distinct, and the list must be sorted alphabetically. The concatenation of the words in the listed order must equal .
If there are several possible dictionaries with the maximum number of words, output any of them.
