| Автор: | А. Кленин, И. Туфанов | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt |
Оргкомитет сборов по программированию знает, что важно организовать правильное питание участников. Еда должна быть вкусной, а блюда — разнообразными. Поэтому разработку меню доверили повару тёте Вале.
Тётя Валя умеет готовить несколько разных блюд. Она использует для их обозначения маленькие английские буквы. Всего в течение сборов будет n приёмов пищи. Тётя Валя составила черновик меню — строку s, состоящую из n маленьких английских букв. Символ si обозначает блюдо, которое она запланировала для i-го приёма пищи.
Черновик меню полностью сбалансирован по всем питательным компонентам, но тётя Валя не особо заботилась о разнообразии.
Помогите тёте Вале сделать меню наиболее разнообразным. Для этого нужно переставить блюда в меню таким образом, чтобы минимальное расстояние между одинаковыми блюдами было как можно больше.
Если существует несколько решений, выведите любое из них.
Входной файл содержит строку s, состоящую из маленьких букв английского алфавита — черновик меню.
Выходной файл должен содержать единственную строку — окончательный вариант меню.
1 ≤ n ≤ 100000;
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|