Задача P. Перемешанные символы

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеется некоторая текстовая строка. Требуется перемешать ее символы таким образом, чтобы исключить цепочки из подряд идущих одинаковых элементов.

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

Входной файл "input.txt" содержит одну единственную строку, состоящую из произвольных печатных символов (ASCII 33-126).

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

Выходной файл "output.txt" должен содержать исходную строку, приведенную к требуемому виду.

В случае, если это невозможно, в выходной файл следует вывести единственный символ пробела (ASCII 32).

Ограничения

Полагается, что длина исходной строки лежит в диапазоне от 1 до 2 ⋅ 107.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
AAAAAbbbbbaaaaaAAAaaaacccAAcccbb
aAabcAabcAabcAabcAabcAabAaAaAbAc
2
32213312222222032022992211222222
 

0.122s 0.027s 15