print2055. Назначения

printНазначения

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Как известно, доктор Хаус очень не любит ждать. Особенно он не любит, когда его пациентам необходимо ждать в очереди на операцию. Обычно с этим проблем не возникает, так как руководство больницы всегда готово пойти на встречу лучшему врачу. Но сейчас, когда Форман уехал на конференцию, Хаусу приходится идти на отчаянные меры.
Недавно в больнице установили новую систему регистрации оперируемых больных. Хаусу пришлось нанять хакера, который взломал эту систему. Выяснилось, что в базе каждое назначение на операцию хранится в виде строки, которая может содержать маленькие латинские буквы, цифры и символ подчеркивания. Однако хакер, в силу невысокой квалификации, может изменять назначение в базе, только удаляя из него все вхождения некоторого символа. Кроме того, оказалось, что из каждой строки в базе можно удалить вхождения только одного символа, так как иначе она признается недействительной.
Доктор Хаус выбрал запись, которую он хочет изменить, и теперь ему интересно, какая лексикографически минимальная строка может из нее получиться.
В первой строке входного файла находится описание назначения на операцию, которое хочет исправить Хаус – строка `s` (`1\ ≤\ |s|\ ≤\ 10^6`), состоящая из маленьких латинских букв, цифр и символов подчеркивания.
В выходной файл выведите лексикографически минимальную строку, которая может получится у доктора Хауса.

Пример ввода 1

house_g_0101_first_january_angioplasty

Пример вывода 1

hose_g_0101_first_janary_angioplasty

Пример ввода 2

khoukse_k_1012_tenth_december_endoscopy

Пример вывода 2

house__1012_tenth_december_endoscopy
Источник: neerc.ifmo.ru/school
loading