B. Минимальная троичная строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана троичная строка (строка, состоящая только из символов '0', '1' и '2').

Можно обменивать местами любую пару соседних (последовательных) символов '0' и '1' (то есть заменять «01» на «10» и наоборот) или любую пару соседних (последовательных) символов '1' и '2' (то есть заменять «12» на «21» и наоборот). Другие обмены запрещены.

Например, со строкой «010210» можно проводить следующие действия:

  • «010210» $$$\rightarrow$$$ «100210»;
  • «010210» $$$\rightarrow$$$ «001210»;
  • «010210» $$$\rightarrow$$$ «010120»;
  • «010210» $$$\rightarrow$$$ «010201».

Заметим, что нельзя менять местами «02» $$$\rightarrow$$$ «20» и наоборот. Также нельзя проводить никаких других операций со строкой, за исключением тех, что описаны выше.

Ваша задача — получить минимальную (лексикографически) строку при помощи некоторого количества описанных выше действий (возможно, нулевого).

Строка $$$a$$$ лексикографически меньше строки $$$b$$$ (если строки $$$a$$$ и $$$b$$$ имеют одинаковую длину), если найдется такая позиция $$$i$$$ ($$$1 \le i \le |a|$$$, где $$$|s|$$$ — длина строки $$$s$$$), что для всех $$$j < i$$$ выполняется $$$a_j = b_j$$$, и $$$a_i < b_i$$$.

Входные данные

Первая строка входных данных содержит строку $$$s$$$, состоящую из символов '0', '1' и '2', ее длина от $$$1$$$ до $$$10^5$$$ (включительно).

Выходные данные

Выведите единственную строку — минимальную (лексикографически) строку, которую можно получить при помощи некоторого количества описанных выше действий (возможно, нулевого).

Примеры
Входные данные
100210
Выходные данные
001120
Входные данные
11222121
Выходные данные
11112222
Входные данные
20
Выходные данные
20