На уроке информатики учитель рассказал Васе про новый вид строк — минимально-символьные строки. Строка называется минимально-символьной, если символ, который встречается в ней минимальное количество раз, единственен. Например, строка "abacaba" — минимально-символьная, потому что единственный символ, который встречается минимальное количество раз в ней — 'c'. В то же время строка "cababac" — не минимально-символьная, потому что символы 'b' и 'c' встречаются в ней минимальное количество раз, то есть не являются единственными.
После урока Вася сразу начал думать над следующей задачей: из данного набора символов составить как можно меньше минимально-символьных строк, используя все символы из набора ровно по одному разу в любом порядке. Вася не смог придумать решение этой задачи, поэтому обратился за помощью к вам. Помогите ему!
Входные данные
В единственной строке входного файла input.txt записана строка s, характеризующая набор символов. Ее длина не превосходит 100.
Выходные данные
В первой строке выходного файла output.txt требуется вывести минимальное количество минимально-символьных строк k, которое можно составить из данного набора символов, использовав каждый символ ровно один раз.
В следующих k строках выходного файла требуется вывести минимально-символьные строки, составленные из данного набора символов.
Если существует несколько правильных ответов, разрешается вывести любой из них.
Пример входных и выходных данных
| Ввод |
Вывод |
| abacaba |
1
abacaba |
| abcabc |
2
abb
acc |
| abc |
3
a
b
c |
| cababac |
2
bcb
acaa |