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