Задача D. Питание программистов

Автор:А. Кленин, И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Оргкомитет сборов по программированию знает, что важно организовать правильное питание участников. Еда должна быть вкусной, а блюда — разнообразными. Поэтому разработку меню доверили повару тёте Вале.

Тётя Валя умеет готовить несколько разных блюд. Она использует для их обозначения маленькие английские буквы. Всего в течение сборов будет n приёмов пищи. Тётя Валя составила черновик меню — строку s, состоящую из n маленьких английских букв. Символ si обозначает блюдо, которое она запланировала для i-го приёма пищи.

Черновик меню полностью сбалансирован по всем питательным компонентам, но тётя Валя не особо заботилась о разнообразии.

Помогите тёте Вале сделать меню наиболее разнообразным. Для этого нужно переставить блюда в меню таким образом, чтобы минимальное расстояние между одинаковыми блюдами было как можно больше.

Если существует несколько решений, выведите любое из них.

Формат входного файла

Входной файл содержит строку s, состоящую из маленьких букв английского алфавита — черновик меню.

Формат выходного файла

Выходной файл должен содержать единственную строку — окончательный вариант меню.

Ограничения

1 ≤ n ≤ 100000;

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
olmkoo
moloko

0.024s 0.006s 15